5
$\begingroup$

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

  • 0
    If a line is horizontal, how do you tell which points are on the left of it, and which points are on the right?2011-07-25
  • 0
    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.2011-07-25
  • 0
    @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$.2011-07-25
  • 0
    @Gerry Myerson: Yes anon's answer is correct, left/right was just the intuition2011-07-25
  • 0
    I think the circle was confusing, I just mean in convex position (but on my paper I always draw them on a circle :-)2011-07-25
  • 0
    Please edit the question so it asks what you really want to ask. For example, put in that restriction forbidding a line through adjacent arcs, a restriction which currently appears only in a comment to an answer.2011-07-26
  • 0
    I've done some major editing in the light of the comments to date (and also I've edited the Tex a bit). If I've done any damage, feel free to roll back and rewrite in your own words.2011-07-26

3 Answers 3

2

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$.

1

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).

  • 0
    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?2011-07-25
  • 0
    @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.2011-07-25
  • 0
    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.2011-07-25
  • 0
    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.2011-07-25
  • 0
    @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.2011-07-25
  • 0
    yes but your construction only yields some minimally separating arrangement of n-1 lines. (For example you miss the one which all the lines are nearly tangential.) For me A, B are distinguishable, if some line in A is different from all the lines in B2011-07-25
  • 0
    @stefan: I don't see the arrangement you describe. The $n-1$ lines cut the circle in $2n-2$ points. If removing any one line puts two of the given points in the same cell, $n-1$ of the intervals between the given points must have just one cutting point, leaving the other $n-1$ in the same interval.2011-07-25
  • 0
    Ross: I think we dont speak about the same problem. So the points are just in convex position, 2 points can lie in the same cell and are not neighboring points. Sorry if this was confusing.2011-07-25
  • 0
    @Ross, I *think* I finally understand the statement of the problem. When stefan says "circle", he means "disk". He's not talking about intervals (or arcs), but connected chunks of the disk. But, stefan, I think $T(4,3)=12$. It's true that there are 16 spanning trees, but only 12 are minimal. In the other 4, you can remove one of the lines and still separate points. Please, please, please edit the question so we can all easily see what you really want.2011-07-26
  • 0
    @Gerry Myerson I'm so sorry for the confusion, I just meant that the points are in convex position (I edited the original post). As for your remark about (4,3) you're right! I should only count the plane embedded spanning trees2011-07-26
0

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$

  • 0
    So, what does this formula give for $n=5$?2011-07-28
  • 0
    It would be: T(5,3) = 20 defining T(0,-1), T(1,0) = 12011-07-28
  • 0
    that's too bad; I think $T(5,3)=15$. I'll add my argument to my answer.2011-07-29
  • 0
    yes you're right, I count some settings multiple times2011-07-31