# Points and lines

I'm interested in the following quantity:

Given $n$ points in convex position (that is, $n$ points in the plane forming the vertices of a convex polygon), how many minimal ways are there to separate those points with lines, s.t. no 2 points fall into the same (possibly infinite) region of the plane.

2 lines are equal, if they induce the same partition of points into two sets.
2 line arrangments are equal if all the lines are equal.

By minimal I don't mean that we only use $n/2$ lines but I mean that the lines are arranged in such a way that, if we remove any line, then at least two points will lie in the same region.

One can separate $n$ points in convex position into $n$ groups using a minimal line arrangement consisting of at least $n/2$ and at most $n-1$ lines.

Let $T(n,m)$ denote the number of possibilities to separate $n$ points in convex position with a minimal line arrangement of $m$ lines.

Im interested in the quantity $T(n,m)$

Does anyone have an idea?

Thank you

-
If a line is horizontal, how do you tell which points are on the left of it, and which points are on the right? – Gerry Myerson Jul 25 '11 at 13:01
OP clearly means two lines are equivalent if they partition the points equivalently. Which side is left and which is right doesn't really matter, so that's more of a language technicality. – anon Jul 25 '11 at 13:20
@Gerry Myerson: pick endpoints for the segments $a$ between $A$ and $B$, $b$ between $B$ and $C$, etc. Then you have $ab, cd$, $ac, bd$, and $ad, bc$, giving $3$, unless you think pairing the points as $ab, cd$ is different from $cd, ab$, in which case there are $6$. – Ross Millikan Jul 25 '11 at 13:20
@Gerry Myerson: Yes anon's answer is correct, left/right was just the intuition – stefan Jul 25 '11 at 13:35
Couldn't this mabye be simplified by projecting the points on the circle to points on a line by a stereographic projection and then defining the speration of the points by 'lines' in a suitable way? – Peter Sheldrick Jul 25 '11 at 17:02

I believe $T(5,4)=55$.

We have a convex pentagon in the plane. Choose a point one each side; call those points $1,2,3,4,5$ in order around the pentagon. By previous discussion, we want to count all the non-self-intersecting spanning trees one can draw on these 5 points, using only line segments between pairs of the points.

There are, up to isomorphism, 3 trees on 5 points; I'll call them X, Y, and I (all to be imagined sans-serif).

There are 5 ways to implement the X; choose any one of the 5 points to be the vertex of order 4, then you have only one way to draw the tree.

To implement the Y, first pick a point to be the vertex of order 3; 5 ways. For concreteness, let's say we have chosen point 1. Now choose the three points to connect to 1. There are 4 ways to do this. If you choose $2,3,4$, then you must connect 4 to 5; if you choose $3,4,5$, then you must connect 2 to 3; that's 10 trees. If you choose $2,3,5$, then you can connect 4 to either 3 or 5; if you choose $2,4,5$, then you can connect 3 to either 2 or 4; that's another 20 trees. All told, 30 ways to implement the Y.

To implement the I, note that the endpoints will either be on adjacent edges of the pentagon, or on edges separated by one edge; we'll call these cases A and B. In either case, we can distinguish one endpoint as the start, the other as the end, by agreeing that the clockwise distance around the pentagon from start to end must be less than half way round the pentagon.

Case A: 5 ways to choose the start, and after that only one way to complete the tree (e.g., if the start is 1, so the end is 2, you must connect 1 to 5, 5 to 4, 4 to 3, and 3 to 2).

Case B: 5 ways to choose the start, and 3 ways to complete the tree. E.g., if the start is 1, so the end is 3, then you can go 1-2-5-4-3, 1-5-2-4-3, or 1-5-4-2-3. (This whole exercise would be so much easier if I knew how to draw and post diagrams).

So, 5 trees in Case A, 15 in Case B, making 20 ways to implement the I, making $$T(5,4)=5+30+20=55$$

EDIT: Now we have enough data to go to the Online Encyclopedia of Integer Sequences, and we find http://oeis.org/A001764 which is said to enumerate non-crossing trees and to be given by ${1\over2n+1}{3n\choose n}$

EDIT 29 July 11: I reckon $T(5,3)=15$.

We have 5 arcs, and 6 ends-of-chords, so one arc has two ends-of chords, the other arcs have one end-of-chord each.

Label the arcs $1,2,3,4,5$ as for the $T(5,4)$ calculation. Assume the arc with two ends-of-chords is arc 1 (then multiply whatever number we get by 5).

The two chords ending on arc 1 could go to arcs 3 and 4. Then the third chord must join arcs 2 and 5.

The two chords ending on arc 1 could go to arcs 2 and 4. Then the third chord must join arcs 3 and 5.

The two chords ending on arc 1 could go to arcs 3 and 5. Then the third chord must join arcs 2 and 4.

No other placement of the two chords ending on arc 1 permits a third chord that separates the vertices, so there are just these three ways. $3\times5=15$.

-

For T(n,n-2) I have the following idea:

If we need n-2 lines this means that (at least) two lines are crossing First we count the number of ways of drawing the 2 crossing lines. This should be $A = n/4 \sum_{i = 3}^{n-1} (i-2)(n-i)$

Lets assume that the 2 crossing lines hit the "circle-segments" a,b,c,d.

Now we have $n-4$ circle-segments left which all need to be connected by a non-crossing tree to either, a,b,c,d. (But a tree, rooted at one of the two crossing lines may intersect the other crossing line.)

Thus we need to count: $B = \sum_{i,j,k,l \in \mathbb{N}, i+j+k+l = n-4} T(i,i-1)T(j,j-1)T(k,k-1)T(l,l-1)$

then $T(n,n-2) = A*B$

-
So, what does this formula give for $n=5$? – Gerry Myerson Jul 28 '11 at 0:35
It would be: T(5,3) = 20 defining T(0,-1), T(1,0) = 1 – stefan Jul 28 '11 at 10:11
that's too bad; I think $T(5,3)=15$. I'll add my argument to my answer. – Gerry Myerson Jul 29 '11 at 4:01
yes you're right, I count some settings multiple times – stefan Jul 31 '11 at 13:01

To get the quantities you cite gives an idea. To get $T(n,n/2) = n!/2^{n/2}$ you put an endpoint between each pair of points on the circle. Any way of connecting those endpoints gives a minimal arrangement, so you just have the number of ordered ways of splitting $n$ into pairs. If you want unordered splits, you have to divide by $(n/2)!$ because any ordering of the pairs gives the same combination. See my comment giving $T(4,2)=3$. To get $T(n,n-1) = (n-1)!$ you put $n-1$ endpoints between one pair of points, then put a single endpoint between each other pair of points. You then have to connect each single endpoint to one of the ones in the group.

However, there is an inconsistency here. In the $(6,3)$ case we considered $ab, cf, de$ different from $bc, ad, ef$ even though they are related by a rotation. By this logic, we should multiply $T(n,n-1)$ by $n$ to pick the segment where the $(n-1)$ points go. Specifying what is the same and what is different is difficult and important in these problems.

To get $T(n,n-2)$ we have to put $n-3$ endpoints in one interval and $n-1$ endpoints in all the other intervals, then connect them up so there are no matches within the $n-3$. This can be done by matching the $n-3$ points each to one of the others, leaving the last pair to connect to each other. This can be done in $(n-1)!/2$ ways. Again, you might multiply by $n$ to pick the interval where the $n-3$ points go (Unless $n=4$ in which case all intervals get a single point).

-
I get only 3 ways to split 4 into pairs. 12/34; 13/24; 14/23. But the formula gives $T(4,2)=6$. And the $T(n,n-2)$ formula gives $T(4,2)=1/2$ - huh? – Gerry Myerson Jul 25 '11 at 13:15
@Gerry Meyerson: In my comment above I show how to get $6$, but I agree $3$ is a better answer. I miswrote my $T(n,n-2)$, see the correction. – Ross Millikan Jul 25 '11 at 13:41
Hi Ross First: I don't distinguish between a line ab-cd and cd-ab. My formula for T(n,n/2) is wrong: because "Any way of connecting those endpoints gives a minimal arrangement..." is not true. I'm for example not allowed to draw a line between two neighboring circle-segments, so I can't just chose an arbitrary endpoint for a line. Now event the T(n,n/2) case seems difficult. T(4,2) = 1 because the "cross" is the only way of obtaining 4 cells with 2 lines. – stefan Jul 25 '11 at 16:37
Concerning the T(n,n-1) construction: I got my result by arguing that any spanning tree between the circlesegments forms a partition using n-1 lines. But I don't understand your argument, to me this only gives n possibilities. – stefan Jul 25 '11 at 16:37
@stephan: I was considering the ordering of the endpoints of the line segments. So for the $(4,3)$ case, think of $a,b,c$ in one segment, and $d,e,f$ one in each other segment. Then you can connect them in six ways. So I would see $T(n,n-1)$ as $(n-1)!$-I will correct my answer. It depends upon what you count as distinguishable configurations. – Ross Millikan Jul 25 '11 at 17:08