ABSTRACT

A crossing family of segments is a collection of segments each pair of which crosses. Given positive integers and, a grid is the union of two pairwise-disjoint collections of segments (with and members, respectively) such that each segment in the first collection crosses all members of the other. Let be the least integer such that any planar set of points in general position generates a crossing family of segments. Also let be the least integer such that any planar set of points in general position generates a -grid. We establish here the facts and.

1. Introduction

For each positive integer let be the least integer such that every planar set of points in general position contains the vertices of some convex n-gon. This number was introduced by Erdös and Szekeres in 1935 (see [1] and [2]) who established the bounds and conjectured that the lower bound is in fact an equality. The values and are easy, and several proofs of the fact have been given. However, no other values have been computed exactly and the upper bound given by Erdös and Szekeres stood until recently as the best known. A seqence of 1998 papers by Chung and Graham [3], Kleitman and Pachter [4], and finally Tóth and Valtr [5] improved the above-mentioned bound to

(0.1)

Morris and Soltan [6] provide an excellent survey of related results.

Given the apparent difficulty of determining values of we might well seek weakened notions of these numbers. For example, let be a combinatorial property satisfied by the vertex set of a convex -gon. It might be interesting to ask how large a set must be to guarantee the existence of a subset of having property. We will consider such generalizations where the property is a specified intersection behavior of some subset of the diagonals to a convex -gon.

We will say that a set generates a collection of segments if each segment in has its endpoints in. Also, we will say that a collection of segments is a crossing family if each pair of segments in crosses (intersects at a point that is not endpoint to either segment). Now if then the vertex set of a convex -gon clearly generates a crossing family of size. Define to be the least integer such that any planar set of points in general position generates a crossing family of segments. Then as we have noted, , but we might expect to be much less. Indeed, the main result in the paper by Aronov et al. [7] implies the much stronger bound

(0.2)

for these numbers. The authors of that paper ask whether this bound might be improved to a linear bound—a question that remains open at present.

Now let and be positive integers. Define a -grid to be a collection of segments

such that each segment s_i crosses each segment but such that segments and are disjoint if, as are and. If then the vertex set of a convex -gon clearly generates a -grid. Define be the least integer such that any planar set of points in general position generates a -grid. We again have the easy inequality, but a result of Nielsen and Sabo [8] implies the linear upper bound

(0.3)

for these numbers.

It appears at least superficially, then, that grids are easier to find than are crossing families, and that both are easier to find than are convex polygons. But while the progression from to to represents a geometric and computational simplification, none of these can be said to be simple. A look at the six-point cases illustrates the situation well.

(A) The value of is not known. It is conjectured that, but (0.1) gives only.

(B) The value of is not known, but we will prove in this paper that.

(C) We will show below that. However, this is the largest case for which the exact value of is known.

The purpose of this paper is to establish the facts mentioned in items (B) (see Section 1) and (C) (see Section 2). Bounds for some of the larger cases of these numbers will be given in a subsequent paper. The methods we use are not complicated, but some imagination is required to find an approach that reduces the number of cases to a manageable level.

2. An Improved Bound for c(3)

The bound (0.2) gives only—of course (from (0.1)) is better. We are able here to improve this substantially to. We would be quite surprised if the actual value of is not closer to the lower bound, but reducing the upper bound appears to be very difficult.

We begin by developing some notation that will be useful in the main proof. Let X be a finite planar set in general position. Now let A and B be vertices of the convex hull of X admitting parallel supporting lines. We may assume these supporting lines touch the convex hull of X only at points A and B so that the points of lie in the strip between them. One of the half-strips bounded by these lines and the segment AB contains at least half the points of. Let this half-strip be called, and let be the number of points of in. We define sequences of sets, and as follows (see Figure 1).

• Let.

• For each such that is defined let be the set consisting of those points in lying on the boundary of the convex hull of, together with the points and. Furthermore, set and.

• Finally, for let be a point of and define to be.

Note then that and that

, so. We think of as being a “convex fence” separating and.

More generally, we will say that a sequence of points from is a -fence for if

• where and• are consecutive vertices on the convex hull of, and

• every segment joining a point of V to a point of W crosses one of the f − 1 segments .

In this case we say that is the set of points of inside the fence and is the of points of outside that fence.

Given positive integers, and we will say that has property if has a - fence consisting of points for some and. The sets described above yield a sequence of properties , for X (where, of course, and f_m = 2).

Lemma 1.1. Let where

for each i and j the segment crosses AB. Then X generates a crossing family of three segments including.

Clearly it is enough to show that is a convex quadrilateral for some, and to do this it is enough to show that line misses segment and line misses segment.

Note that the halfplane determined by and containing is divided into four (or fewer) regions by the lines, , and. Suppose first that one of these regions contains both and. Now cannot intersect all three sides of the triangle, so it misses some segment. From our observation above the points generate a crossing family of six segments.

If none of these regions contains two of the points of then it must be the case that there is a segment meeting exactly two of the lines, ,. But then cannot meet any of the sides of the triangle (since it cannot meet only one side of the triangle and there are two triangle sides that it clearly cannot meet, having crossed the lines determined by these sides at points outside of the triangle). But now misses one of the lines, so we once again have the situation described above.

Lemma 1.2. If a set X has property (with and) and generates no crossing family of three segments then also has property .

Proof. Let be a -fence for X with related components V and W. Order the points of radially from as

(see Figure 2).

Now X generates no crossing family of three segments by assumption, so by Lemma 1.1 there cannot be three points of on the same side of line as point. (Again see Figure 2—the segment is crossed by every segment joining such a point of to any one of, , or.) But then is a fence with related components and.

Lemma 1.3. Any set having property for some generates a crossing family of three segments.

Proof. Assume to reach a contradiction that a set

has property for some but generates no crossing family of three segments. Then by Lemma 1.2 X also has property. But by Lemma 1.1 any set with property will generate a crossing family of three segments—a contradiction.

These lemmas establish that a set generates a crossing family of three segments if it contains a subset with a -fence of two points or a -fence of three points. This fact will be used repeatedly in our next proof.

Theorem 1.4..

Proof. The lower bound is established by considering the set of eight points depicted in Figure 3. (A few lines are shown to indicate relative positioning of the points.) We leave it to the reader to verify that this set fails to generate any crossing family of three segments.

Now let X be any set of 16 points in general position. We will show that X generates a crossing family of three segments. The construction given at the outset of this section established a sequence,

, , ,

of properties for. Consider the property.

We may clearly assume else contains the vertices of a convex hexagon and thus clearly generates the desired crossing family. If then we have either or, either of which guarantees the crossing family by our preliminary lemmas. It remains, then, to examine the cases and.

Case 1:

In this case, has property. As in Figure 4, let the fence be and consider the four regions, , , and as shown. Let denote the number of points of in region, so that.

If r₁ > 0 and r₃ > 0 (or similarly if r₂ > 0 and r₄ > 0) it is easy to see that X then generates a crossing family of three segments (two of which are AC and BD). So, if r₁ > 0 then we may assume either or. This means either ACD or ABD is a -fence, so our

preliminary lemmas would guarantee the desired crossing family for X. Thus, we may assume and.

If then (using the points in and along with points B and D) AC is a -fence. On the other hand, if then ACD is a -fence. So (again using our lemmas) we may assume.

Subcase 1A:,

Order the points of in regions and as radially from as in Figure 5. We may assume that the region in that figure (bounded by, , and the supporting line through to the convex hull of) contains at most two points of, else is a -fence (with the latter set of three points being). But then is a - fence where the points inside consist of the points in region less (if) and the points outside consist of the (at least three) points outside ABCD not lying in together with D and the point of X in region. By our preliminary lemmas, X then generates a crossing family of three segments.

Subcase 1B:,

Consider now the region in Figure 6 (bounded by, , and the supporting line). If this region contains two points of X then BD is a -fence where one set of three points is and the other consists of the two points in together with point A. Thus, we may assume contains no more than one point of X.

This shows that by discarding up to two points (and) inside and one point (in) outside the fence we can eliminate all segments (joining an inside point to an outside point) that cross AB. A mirror image of this same argument can be done for eliminating segments that cross CD. In this way we conclude that we can discard four points inside ABCD and two points outside ABCD and eliminate all segments except those that cross BC. So, BC is a -fence for the remaining subset of X. As before, this is sufficient to guarantee that X generates the desired crossing family.

Case 2:

In this case, X has property. Consider the convex hull of the five points making up the fence. The diagonals of this pentagon determine eleven interior regions. If a point of X lies in any of the

five regions bounded by segments of the pentagon or in the central region bounded by all the diagonals, then generates a crossing family of three segments as shown in Figure 7.

Thus, we may assume that the six points of inside the fence lie in the five regions labeled through in Figure 8. As before, let denote the number of points of in region.

• If points of X lie in each of two adjacent regions from among R₁ through R₅ then it is easy to construct a crossing family of three segments (two are diagonals of ABCDE and the other joins the points in question).

• If then ACE is a -fence—more than enough to guarantee the desired crossing family.

Putting together these two observations, we may now assume that, , either or, and (of course).

• If then AC is a -fence where on one side we include two of the points from region along with B and on the other side we include a point from along with D and E.

• If then either R₄ or R₅ contains 5 points of X. If R₄ contains these points then CE is a -fence where the three points on one side consist of the point in R₂ together with A and B. If the points lie in R₅ then similarly AD is a -fence.

Both of the above cases, then, lead to a crossing family of three segments generated by X. The only remaining case to consider is (and). Here, ABDE is a -fence for X (where we include C with the points outside the fence). Note that Lemma 1.2 would allow us to conclude that either X generates a crossing family of three segments or else its property

must imply property (and

). Unfortunately, that is not sufficient under our lemmas to give the desired conclusion. Instead, we will need to be more careful in reducing the fence.

For our first step in the reduction, order the points of X in region as through radially from B as in Figure 9. We may assume the region in that figure contains no more than one point of X, since otherwise BE is a -fence (with two points from and A on one side and on the other). Then discarding any point in along with and, we may eliminate all segments (joining a point inside to a point outside) that cross; all this while leaving at least four inside points and at least five outside points.

The second part of the reduction is accomplished by ordering the remaining points of X in R₂ as Q₁ through Q₄ radially from D as in Figure 10. We may assume the region labeled as S₂ in that figure contains no more than 2 points of X, else is a -fence (with three points from S₂ on one side and on the other). Thus, discarding points in along with Q₁, BD is now a -fence for the remaining set, and our reduction is complete.

We have demonstrated that in every possible case the set X must generate a crossing family of three segments, so the theorem is proved.

3. An Exact Value for #(1,2)

Here we prove the only exact value known for any of the six-point configuration numbers mentioned in the introduction. The following well-known fact will prove useful in the analysis.

Lemma 2.1: Suppose that

where for each and j the segment crosses AB. Then X generates a -grid consisting of n pairwise disjoint segments

each of which crosses.

Proof. Let π be the permutation of such that the sum of the lengths of the segments is minimized. Then the segments

form a -grid.

Theorem 2.2:.

Proof. Figure 11 shows a set of seven points that generates no -grids. (This is easily checked by hand.)

It remains to prove that any set of eight points in general position will generate a -grid. Let be any such set, let be a vertex of the convex hull of, and let. We consider several cases depending on the shape of the convex hull of.

Case 1. If the convex hull of is a 6-gon or 7-gon then clearly generates a -grid.

Case 2. Suppose the convex hull of is a 5-gon with the remaining points of being P and Q. If P and Q lie on opposite sides of any diagonal to ABCDE then generates a (1,2)-grid by Lemma 2.1. Consequently, we may assume that P and Q lie in the “inner pentagon” determined by the diagonals. We may also assume that Q is interior to the triangle PAB. But then QD crosses both the diagonal CE and either PA or PB, giving us a (1,2)-grid (see Figure 12).

Case 3. If the convex hull of is a quadrilateral ABCD then the three points must be distributed between the four regions determined by the diagonals of. By Lemma 2.1 we may assume that these points are not separated by either diagonal—thus all lie in the same region.

Assume then that P, Q, and R are each interior to both triangles ABC and BCD. If points form the vertices of a convex quadrilateral then its diagonals together with segment BD form a -grid (see the left

half of Figure 13). Thus, we may also assume that R is interior to the triangle APQ as in the right half of Figure 13. We now consider some subcases. Recall that there is a point Z of set X lying outside of the convex hull of. The segment RZ must meet either BC or one or both of the diagonals of ABCD.

Subcase 3A. Suppose first that RZ meets BC. Note that it must also meet one of the sides of triangle APQ, and that this side is disjoint from BC. Thus X generates a (1,2)-grid in this case.

Subcase 3B. Next suppose that RZ meets exactly one of the diagonals of ABCD. Then these diagonals together with RZ form a (1,2)-grid.

Subcase 3C. Finally, suppose that RZ meets both diagonals of ABCD. In particular, then, RZ meets BD. But BD meets both AP and AQ, and RZ must miss one of these. So, this case also yields a generated (1,2)-grid.

Case 4. The only remaining case is to assume that the convex hull of is a triangle, say ABC, with the four remaining points of interior to this triangle. If ZABC is a convex quadrilateral then by separating B from the remaining seven points we reduce to one of the earlier cases (see Figure 14).

Thus we may assume that C is interior to triangle ZAB (so that the convex hull of X is a triangle). We may clearly assume that a similar configuration results if any of the three vertices of this triangle are separated from the other seven points. In this case the set X must be as pictured in Figure 15: the convex hull of X is a triangle and the convex hull of is a triangle with as the third vertex. Two points of X, say P and Q, must lie in the region common to the interiors of triangles, , and. We consider two subcases for the placement of these points.

Subcase 4A. First it is possible that either P or Q is not interior to triangle. Assume, for instance, that segment separates P from as in Figure 16. In this case meets both and one of or, yielding a (1,2)-grid.

Subcase 4B. Finally, assume both P and Q lie interior to triangle. The ray PQ must meet one of the sides of this triangle, say. Then Q is interior to triangle so we have the configuration depicted in Figure 17. The segment must now meet a side

of each of the triangles and, again yielding a (1,2)-grid.

All cases have now been considered and the proof is complete.

REFERENCES