Lines on a circle - a counting problem

genericusrnme

So over the course of yesterday and the day before that I've spent a few hours thinking about these problems;

1. Given a circle, place n points arbitrarily* on the edge and connect every point to every other point with a straight line. How many intersections do you get?
2. Given the same situation described above, how many m-gons** are formed?

*I'm going to discount any configuration where three or more lines intersect at one point however
**I'm only counting m-gons that don't have any lines passing through them, so I'd count two triangles stuck together at the hypotenuse as two 3-gons rather than two 3-gons and a 4-gon etc.

Now the first problem I solved fairly easily (it looks a little messy, the LaTeX sticks out like a sore thumb)
.

Take n points on a circle and label them, starting from some arbitrary point 1,2...n in a clockwise fasion and let the lines [itex]L_{a,b}[/itex] be the lines from point labeled by a to the point labeled by b where a<b. Let the number of intersections of the [itex]\left(
\begin{array}{c}
n \\
2
\end{array}
\right)[/itex] lines be denoted by [itex]\Gamma[n][/itex]. *For a line [itex]L_{a,b}[/itex] to intersect a line [itex]L_{c,d}[/itex] the points a and b must be on opposite sides of [itex]L_{c,d}[/itex]. Let [itex]\mathcal{A}[/itex] be the set of labels of points on the circle and let us define the left set of the line [itex]L_{c,d}[/itex], [itex]\mathcal{L}\left[L_{c,d}\right][/itex] as the set [itex]\{n\in \mathbb{N} : c < n < d\}[/itex] and naturally the right set [itex]\mathcal{R}\left[L_{c,d}\right][/itex] as [itex]\mathcal{A}-\{c,d\}\cup \mathcal{L}\left[L_{c,d}\right][/itex].

Let [itex]\Gamma[n-1][/itex] be given. Suppose we add one more point with the label n, since the labeling started at an arbitrary point we can always let the added point be n. If we let [itex]\gamma[n][/itex] be the number of new intersections when all possible lines from n are added we must have [itex]\Gamma[n] = \Gamma[n-1] + \gamma [n][/itex] and so we shall have a recurrence relation.
Since we require, for an intersection, that there is at least one point on each side of the line there must be no intersections on the lines [itex]L_{n-1,n}[/itex] and [itex]L_{1,n}[/itex] since [itex]\mathcal{L}\left[L_{n-1,n}\right]=\emptyset[/itex] and [itex]\mathcal{R}\left[L_{1,n}\right]=\emptyset[/itex]. Next let is define the number of 'free points' as [itex]m = \left|\mathcal{L}\left[L_{a,b}\right]\cup \mathcal{R}\left[L_{a,b}\right]\right| = n -2[/itex] and since [itex]\mathcal{L}\left[L_{a,b}\right]\cap \mathcal{R}\left[L_{a,b}\right]=\emptyset[/itex] this implies [itex]\left|\mathcal{L}\left[L_{a,b}\right]\right| + \left|\mathcal{R}\left[L_{a,b}\right]\right| = m[/itex] for any line. We also see that [itex]\left|\mathcal{L}\left[L_{a,b}\right]\right|= b - a-1[/itex] from the definition.
To find [itex]\gamma[n][/itex] we take a point labeled by a and let [itex]l[a][/itex] be the number of lines from [itex]\mathcal{L}\left[L_{a,n}\right][/itex] to [itex]\mathcal{R}\left[L_{a,n}\right][/itex], each of which must then intersect [itex]L_{a,n}[/itex], so [itex]\gamma [n] = \sum _a l[a][/itex]. For each a [itex]l[a][/itex] has [itex]\left|\mathcal{L}\left[L_{a,n}\right]\|\mathcal{R}\left[L_{a,n}\right]\right| = (n-a-1)(a-1)[/itex] and so [itex]\gamma [n] = \sum _{a=1}^m (n-a-1)(a-1)=\sum _{a=1}^m a(m-a)[/itex].

Which gives the relation, using the fact that [itex]\Gamma[3]=0[/itex]
[itex] \Gamma [n]=\Gamma [n-1]+\sum _{a=1}^m a(m-a)[/itex]
[itex]= \Gamma [n-2]+ \sum _{a=1}^{m-1} a(m-1-a) + \sum _{a=1}^m a(m-a)=\text{...}[/itex]
[itex]= \sum _{p=0}^{n-4} \sum _{a=1}^{n-2-p} a(n-2-p-a)[/itex]
And after a little work
[itex]\Gamma[n] = -\frac{n}{4}+\frac{11 n^2}{24}-\frac{n^3}{4}+\frac{n^4}{24}[/itex]

*I believe an application of the mean value theorem would guarantee an intersection here
.

It seems to me that [itex]\Gamma[n][/itex] should be correct for the boundary of any convex space (I'm not sure if this is the correct term, I mean the one where a straight line can be drawn from any point to any other point without leaving the space) subset of [itex]R^2[/itex] and (I'm guessing) by extention anything isomorphic to a convex subset of [itex]R^2[/itex]

The second one however is giving me a little trouble. I've played about a little with n≤10 points on a cirlce and I've managed to work out how to;
1. Count the sum of the internal angles which I got to be [itex]\alpha[n] = (n-2)\pi + 2 \pi \Gamma[n][/itex]
2. Count the total number of corners which I got as [itex]\mathcal{C}[n]=4\Gamma [n]+n(n-2)[/itex] which is just 4 corners for every intersection and around the edge each point has n spewing forth which gives n-2 conrners, n points = n(n-2) extra corners.
3. Find the number of polygons given n points which I got as [itex]\Sigma [n]=1-\frac{7 n}{4}+\frac{23 n^2}{24}-\frac{n^3}{4}+\frac{n^4}{24}[/itex] which I got in virtually the same way I counted the total number of intersections, the outer two lines give 1 extra 3-gon and every other line gives the number of new intersections + 1 extra polygons

I also noted that the no. m-gons seems to be monotonic increasing but I have no idea how I could get started on proving that, I'm also conjecturing that as long as three or more lines don't intersect at one point the number of m-gons is invariant under moving the n points around the boundary again I'm not sure how to prove this, all I've got is that the total number of polygons is invariant.
But just with 3 conditions I can only solve for n=6 (since polygons only start appearing at n=3), so I need a better approach than just trying to find more 'conserved quantities'.

Any hints as to where I could go next?
I'm running a little low on ideas

(I apologise if I missed something, this is turning into an essay )

haruspex

Wrt the first problem, there's a much easier way. Think about taking four vertices at random. How many intersections are made by just the lines joining them? How many choices of 4 vertices give rise to a given intersection? I think you'll find your formula factorises nicely.
But I don't think this approach carries over to the second problem. It might but for the 'no cut m-gons' rule.

genericusrnme

Yeah, I noticed that it factorised into n(n-1)(n-2)(n-3)1/4! = n choose 4, it actually came to mind as soon as I had finished doing it the way I did it first (which looks a lot more involved than it actually was) lol.
The reason I kept with that approach is because I thought it might be more useful to keep track of what points are on what side of the lines as I did find a way to count the number of 3-gons in n=6 iirc using this but that method failed to carry on to greater n.

And yeah, that's the reason I didn't want any cut m-gons, seemed like it'd end up being a little too easy.

haruspex

The total number of regions is easy (and a well-known problem), but you want it broken down by numbers of sides, right? I'm not sure that's well-posed. At n=7, it looks like the counts can vary depending on exactly how the points are placed.
I have calculated the total number of sides. Asymptotically, the average is 4 sides to a region.

genericusrnme

I've already worked out the total number of regions.

Are you sure about that part?
From my limited patience to sit and draw out circles and draw lines across them it did seem like the number of m-gons remained the same. Although I didn't have time to try every possible configuration to be sure.
Could I ask how you came to this conclusion? (not that it'd surprise me I was expecting this to be the case before I started playing about with it)

I already got this part too

Thanks for the input btw, I really appreciate it!

HallsofIvy

"Arbitrarily" is too vague here. You want to specify, for example , that the points are NOT equally spaced but spaced so that you never have three or more lines intersecting in a single point. This is an old problem designed to be misleading. With two points you get one line dividing the circle into 2 areas (NOT 'm-gons' since they have a curved edge), with 3, you get 3 lines, dividing the circle into 4 areas, with 4 points you get 6 lines dividing the circle into 8 areas, with 5 points, 16 areas which lead one to guess that n points will give [itex]2^{n-1}[/itex] areas. But if you do 6 points and count areas carefully, you get 31 areas, not 32. The correct formula for n points is
[tex]\sum_{i=0}^5\begin{pmatrix}n-1 \\ i\end{pmatrix}[/tex]
if n is less than or equal to 5, this gives the entire binomial expansion of [itex](1+ 1)^{n-1}= 2^{n-1}[/itex] but if n is greater than 5, only part.
Now the first problem I solved fairly easily (it looks a little messy, the LaTeX sticks out like a sore thumb)
.

Take n points on a circle and label them, starting from some arbitrary point 1,2...n in a clockwise fasion and let the lines [itex]L_{a,b}[/itex] be the lines from point labeled by a to the point labeled by b where a<b. Let the number of intersections of the [itex]\left(
\begin{array}{c}
n \\
2
\end{array}
\right)[/itex] lines be denoted by [itex]\Gamma[n][/itex]. *For a line [itex]L_{a,b}[/itex] to intersect a line [itex]L_{c,d}[/itex] the points a and b must be on opposite sides of [itex]L_{c,d}[/itex]. Let [itex]\mathcal{A}[/itex] be the set of labels of points on the circle and let us define the left set of the line [itex]L_{c,d}[/itex], [itex]\mathcal{L}\left[L_{c,d}\right][/itex] as the set [itex]\{n\in \mathbb{N} : c < n < d\}[/itex] and naturally the right set [itex]\mathcal{R}\left[L_{c,d}\right][/itex] as [itex]\mathcal{A}-\{c,d\}\cup \mathcal{L}\left[L_{c,d}\right][/itex].

Let [itex]\Gamma[n-1][/itex] be given. Suppose we add one more point with the label n, since the labeling started at an arbitrary point we can always let the added point be n. If we let [itex]\gamma[n][/itex] be the number of new intersections when all possible lines from n are added we must have [itex]\Gamma[n] = \Gamma[n-1] + \gamma [n][/itex] and so we shall have a recurrence relation.
Since we require, for an intersection, that there is at least one point on each side of the line there must be no intersections on the lines [itex]L_{n-1,n}[/itex] and [itex]L_{1,n}[/itex] since [itex]\mathcal{L}\left[L_{n-1,n}\right]=\emptyset[/itex] and [itex]\mathcal{R}\left[L_{1,n}\right]=\emptyset[/itex]. Next let is define the number of 'free points' as [itex]m = \left|\mathcal{L}\left[L_{a,b}\right]\cup \mathcal{R}\left[L_{a,b}\right]\right| = n -2[/itex] and since [itex]\mathcal{L}\left[L_{a,b}\right]\cap \mathcal{R}\left[L_{a,b}\right]=\emptyset[/itex] this implies [itex]\left|\mathcal{L}\left[L_{a,b}\right]\right| + \left|\mathcal{R}\left[L_{a,b}\right]\right| = m[/itex] for any line. We also see that [itex]\left|\mathcal{L}\left[L_{a,b}\right]\right|= b - a-1[/itex] from the definition.
To find [itex]\gamma[n][/itex] we take a point labeled by a and let [itex]l[a][/itex] be the number of lines from [itex]\mathcal{L}\left[L_{a,n}\right][/itex] to [itex]\mathcal{R}\left[L_{a,n}\right][/itex], each of which must then intersect [itex]L_{a,n}[/itex], so [itex]\gamma [n] = \sum _a l[a][/itex]. For each a [itex]l[a][/itex] has [itex]\left|\mathcal{L}\left[L_{a,n}\right]\|\mathcal{R}\left[L_{a,n}\right]\right| = (n-a-1)(a-1)[/itex] and so [itex]\gamma [n] = \sum _{a=1}^m (n-a-1)(a-1)=\sum _{a=1}^m a(m-a)[/itex].

Which gives the relation, using the fact that [itex]\Gamma[3]=0[/itex]
[itex] \Gamma [n]=\Gamma [n-1]+\sum _{a=1}^m a(m-a)[/itex]
[itex]= \Gamma [n-2]+ \sum _{a=1}^{m-1} a(m-1-a) + \sum _{a=1}^m a(m-a)=\text{...}[/itex]
[itex]= \sum _{p=0}^{n-4} \sum _{a=1}^{n-2-p} a(n-2-p-a)[/itex]
And after a little work
[itex]\Gamma[n] = -\frac{n}{4}+\frac{11 n^2}{24}-\frac{n^3}{4}+\frac{n^4}{24}[/itex]

*I believe an application of the mean value theorem would guarantee an intersection here
.

It seems to me that [itex]\Gamma[n][/itex] should be correct for the boundary of any convex space (I'm not sure if this is the correct term, I mean the one where a straight line can be drawn from any point to any other point without leaving the space) subset of [itex]R^2[/itex] and (I'm guessing) by extention anything isomorphic to a convex subset of [itex]R^2[/itex]

The second one however is giving me a little trouble. I've played about a little with n≤10 points on a cirlce and I've managed to work out how to;
1. Count the sum of the internal angles which I got to be [itex]\alpha[n] = (n-2)\pi + 2 \pi \Gamma[n][/itex]
2. Count the total number of corners which I got as [itex]\mathcal{C}[n]=4\Gamma [n]+n(n-2)[/itex] which is just 4 corners for every intersection and around the edge each point has n spewing forth which gives n-2 conrners, n points = n(n-2) extra corners.
3. Find the number of polygons given n points which I got as [itex]\Sigma [n]=1-\frac{7 n}{4}+\frac{23 n^2}{24}-\frac{n^3}{4}+\frac{n^4}{24}[/itex] which I got in virtually the same way I counted the total number of intersections, the outer two lines give 1 extra 3-gon and every other line gives the number of new intersections + 1 extra polygons

I also noted that the no. m-gons seems to be monotonic increasing but I have no idea how I could get started on proving that, I'm also conjecturing that as long as three or more lines don't intersect at one point the number of m-gons is invariant under moving the n points around the boundary again I'm not sure how to prove this, all I've got is that the total number of polygons is invariant.
But just with 3 conditions I can only solve for n=6 (since polygons only start appearing at n=3), so I need a better approach than just trying to find more 'conserved quantities'.

Any hints as to where I could go next?
I'm running a little low on ideas

(I apologise if I missed something, this is turning into an essay )[/QUOTE]

genericusrnme

I think you made a little mistake with your QUOTE tags

I said m-gons because I didn't want to include the parts with circular edges although it'd just be a matter of adding n onto the formula I got for the number of m-gons as far as I can see and I think the description I gave where I just don't include configurations where three or more lines intersect at one point is better since this can happen even when the points aren't equally spaced.

For n=6 your formula gives
[itex]\sum_{i=0}^5\begin{pmatrix}6-1 \\ i\end{pmatrix}=32[/itex]

whereas if we add n to what I got you get 31 for n=6...

haruspex

Put 7 points equally spaced around. (No three lines intersect at one point.) The central region has 7 sides and is surrounded by 7 triangles and (touching at vertices) 7 pentagons. Consider one of these triangles. It is surrounded (including touching at vertices) by regions with the following numbers of sides: 7, 3, 5, 4, 5, 3.
Take the endpoints of the line separating this triangle from the central heptagon and slide them equally so as to make the triangle shrink to a point. I believe that no other triple of lines comes to intersect in a single point in the process. Move the line just a fraction further and the triangle reappears, reversed. It is now surrounded by regions with these numbers of sides: 6, 4, 4, 5, 4, 4.
Re HofI's sum, it should be i = 0 to 4, not 0 to 5.

haruspex

I've attached a diagram of the 7 points not quite equally spaced.

Attached Files

heptagon.doc (12.0 KB, 1 views)

genericusrnme

Oh, well damn!
I never thought of that one

I guess I'll have to give up on my search with n 'arbitrary' points.

You and HallsofIvy both have mentioned that this is an old/well known problem so I'm wondering what the name of the problem is?

haruspex

If you Google "number of regions lines circle" you should see plenty of hits.