Dividing circle into pieces by choosing points on circumference?

Question

On a circle, N arbitrary points are chosen on its circumference. The complete graph formed with those N points would divide the area of the circle into many pieces.

What is the maximum number of pieces of area that the circle will get divided into when the points are chosen along its circumference?

Examples:

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

Any ideas how to go about this?

Answer 1

This is known as Moser's circle problem.

The solution is:

i.e.

The proof is quite simple:

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

Now, how many edges does each vertex touch? Well, it's a complete graph, so each vertex on the outside touches n - 1 edges, and of course each vertex on the inside touches 4 edges. So the number of edges is given by (n(n - 1) + 4(n choose 4))/2 (we divide by two because otherwise each edge would be counted twice by its two vertices).

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

Solving for f gives the formulae above :-)