Dividing a circle into pieces, choosing points around a circle?

Question

On a circle, N arbitrary points are selected along its circle. A complete graph formed with these N points would divide the area of ​​the circle into many parts.

What is the maximum number of parts of the area over which the circle will be divided by when the points are selected along its circle?

Examples:

• 2 points => 2 parts
• 4 points => 8 pieces

Any ideas how to do this?

Answer 1

This is called the Moser circle problem .

Decision:

i.e.

The proof is simple enough:

Consider each intersection inside the circle. It should be determined by the intersection of two lines, and each line has two points, so each intersection inside a circle defines 4 unique sets of points on a circle. Therefore, there are at most n choose 4 inner vertices and, obviously, there are n vertices on the circle.

Now, how many edges are associated with each vertex? Well, this is a complete graph, so every vertex on the outside touches edges n - 1 , and, of course, every vertex on the inside touches edges 4 . Thus, the number of edges is set (n(n - 1) + 4(n choose 4))/2 (we divide by two, because otherwise each edge will be considered twice as its two vertices).

The last step is to use the Euler formula for the number of faces in the graph, i.e. v - e + f = 1 ( Euler characteristic 1 in our case).

The solution for f gives the above formulas :-)