points in a plane

[BMAD]

Suppose there are 6 points in a plane.  What is the most amount of edges that could be used to connect the points (without overlapping)?  What if there were 7 points? 8 points? n points?

[BMAD]

to be clear, for edges, i mean straight line segments and the plane is 2d.

Edited March 16, 2016 by BMAD

[bonanova]

Here's a quick response, that may be way off
 

Spoiler

Make a convex polygon out of (n-1) of the points, and put the nth point inside.

The perimeter comprises (n-1) edges. The "spokes" comprise another (n-1) edges.

So 2(n-1) is a lower bound.

Now modify the polygon, making it star-like and connect every other point, adding Floor [(n-1)/2] edges.

Final answer: Floor [5(n-1)/2] edges.

 

[I_only_signed_up_for_this]

The best solution I can get is 2n for 6, and 2n + 1 for everything else. Put a polyhedron inside of another polyhedron.

[BMAD]

On 3/16/2016 at 5:32 PM, bonanova said:

Here's a quick response, that may be way off
 

  Reveal hidden contents

Make a convex polygon out of (n-1) of the points, and put the nth point inside.

The perimeter comprises (n-1) edges. The "spokes" comprise another (n-1) edges.

So 2(n-1) is a lower bound.

Now modify the polygon, making it star-like and connect every other point, adding Floor [(n-1)/2] edges.

Final answer: Floor [5(n-1)/2] edges.

I played with your solution.  Is there a condition missing?  It doesn't seem to hold for small n.

 

[BMAD]

I have

Spoiler

when v > 2, edges = 3(vertex count) - 6

 

[bonanova]

I think your formula is correct.

Spoiler

My formula is correct for 6 and 7 points, but is low for 8 and 9 points.
For 9 points, my formula says 20, but I get 21 edges.
For 8 points, my formula says 17 but I get 18.
Your formula correctly gives 21 and 18.

Do you have a proof?

Spoiler

A simple construction shows that adding a point to an already optimal layout always permits 3 additional edges.

 

[BMAD]

1 hour ago, bonanova said:

  Hide contents

 

Do you have a proof?

  Hide contents

A simple construction shows that adding a point to an already optimal layout always permits 3 additional edges.

In optimal (most edges being used) form, every new point after the fourth one will only add three edges. Making a chart of vertices to edges, one can see a linear relationship of vertices to edges (if you exclude the 1 & 2 vertices options).

 

Edited April 2, 2016 by BMAD
Grammar