Cutting up a circle

Suppose you have a circle. Choose a number of points on the edge of it, then join all these points to each other and see how many pieces the circle is split into. So for instance:

The cases with four and five points

When there are four points, there are 8 areas (left), and when there are five points there are 16 areas (right)

Obviously when you choose three points on the side you just have a triangle in a circle, which has 4 areas. When you choose two points on the side you just split the circle in half, giving you two areas.

It really looks like each time we add a point, we double the amount of areas we have. But in fact, this does not hold.

Now when we choose six points things are a little bit more complicated because depending on how you do it, you might get different numbers of areas. The picture below shows this:

When there are six points, there are can different numbers of areas

Look at the red lines. On the left they form a triangle, whilst on the right they meet at a single point. This means the diagram on the right has one less area than the one on the left.

To save you counting, the diagram on the left has 31 areas and the diagram on the right has 30 areas. By our pattern we would expect at least one of them to have 32, so that has gone out the window!

To get the most number of areas possible, we should never allow any three lines to meet at a single point (except for the at the points at the edge of the circle). Let’s carry on thinking about the maximum number. So the table goes:

The '31' just messes everything up...

So what about the 100th? We certainly can’t be bothered to draw a diagram for it. I guess the answer is to do some mathematics!

Euler’s Formula

There is a well known theorem, first stated by Euler and first proven by Cauchy. It says that if you have a diagram (graph) that you can draw on paper without any lines crossing, then the number of faces is equal to two more than the number of edges joining the points minus the number of points (known as vertices). That is:

F = E-V+2

For a proof and more information, look here.

Applying Euler’s Formula

The problem is, our diagram usually can’t be drawn without any of lines crossing each other. In fact, the lines crossing each other to make new areas is exactly what this is about! But what we can do is add new vertices in so that it can. Thus, every time that two lines cross we add a point at their intersection. For instance:

We can add vertices

Here we add vertices to the graph so that no line crosses another (except at a vertex)

Now to use the formula to find out how many faces we have, we must first find out how many vertices we have now, and how many edges we have now.

Finding the number of vertices

We started with n vertices on the edge. How about the extra ones we added? Well, if you choose 4 different points on the edge then in the original version (before we added all the extra vertices), two of the lines connecting them would have to meet in a point. (Not any two of the lines, just a particular two. This is because you cannot draw the circle with 4 points without exactly one line crossing.) For instance:

 

If you select four points, two lines connecting them always cross

If you select four points, two lines connecting them always cross. For instance, the 4 points in red have the following two lines in green cross, but no other lines connect them do.

Each crossing can also be related to two lines, and hence four points. Therefore there are exactly as many meeting points as there are ways to choose 4 points from n. That is, there are:

n choose 4Adding in the n vertices we started with (the ones on the edge of the circle, remember?) we get:

V = n + (n choose 4)

Finding the number of edges

We’re going to split the edges into three types. Those that connect vertices on the edge to other ones on the edge (directly), those which connect internal vertices to ones on the edge, and those which connect internal vertices together. That is:

Edges that go from one vertex on the circle to its immediate neighbour are definitely uncut. There are n of those. They are the blue lines on here:

The edges around the circle

The blue lines show the edges which connect vertices on the edge and are definitely uncut. There is one for each vertex on the circle

And so straight away we have:

There are n edges connecting the original verticesNow let us consider the number of edges that connect a vertex on the edge of the circle to one of the new ones on the inside.

Look at the picture below. Notice that one of the original lines is highlighted in red. It cuts through a number of lines and so and two ends of it are edges which connect the dots on the edge of the circles to one of the dots on the inside.

An example of a chord

The red line is a chord

Now each of the original lines gives us two of these edges. So how many of the original lines are there? Well, there are as many as there are ways of choosing 2 points from n. That is,

n choose 2

However, this is wrong because it counts even the lines which were shown in blue above! These lines don’t cut anything and so should be excluded. Because there were n of them, that means that the actual number of edges that contribute is:

(n choose 2)-nAnd so, as each line gives us two edges which connect points on the circle to the inside, the number of these are:

2*[(n choose 2)-n]We now only have the final category of edges to go: Finding the number of edges which connect vertices on the inside to other vertices on the inside. The number of vertices on the inside of the circle was found earlier to be:

n choose 4

Now, each vertex has four edges connected to it, from the two lines which intercept it. So, think about the following number, which is four times the number of vertices inside the circle:

4*(n choose 4)This number is counts four times the number of vertices inside the circle.

Connections of edges from internal points

The green and the red points share an edge, so internal edges are overcounted

In the picture above, two vertices are considered. One of them, the green one, only connects to other internal vertices. The red one connects to three internal internal vertices and one on the circle. The green and the red also connect to each other and so you can see that the internal edges will each be counted twice. On the other hand, the edges which connect internal vertices to those on the circle are only counted once.

Therefore we have a formula:4*(n choose 4) = 2 * (edges connecting internal vertices together) + (edges connecting internal vertices to those on the circle)Now the term on the end was found above, and so we can substitute it in and rearrange to give:

Internal edges = 2(n choose 4)-(n choose 2)+nAdding all these terms together, the number of edges is then:

E = 2(n choose 4) + (n choose 2)

So that is all the extra edges we have added. But in fact, we are missing some edges! Why? The circle itself! If we are considering the whole thing as a graph we should treat the circle itself as n edges. And so, in fact…

real E = 2(n choose 4) + (n choose 2) + nAll in all

All that is left to do is apply the formula!

F = (n choose 4) + (n choose 2) + 2

Except you must remember that one of those areas is the area around the circle, and so the actual numbers of areas is:

Areas = (n choose 4) + (n choose 2) + 1

(When n is 100 this is equal to 3 926 176, to answer the question at the start)

Here is the graph of this function:

A graph of the number of areas cut by the circle against the number of points on the side

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: