Halving Lines and k-sets

Let S be a set of n points in the plane. A halving line is a line through two points in S that splits the remaining points into two equal-sized subsets. How many halving lines can S have? More generally, a k-element subset of S is called a k-set if it is the intersection of S with a halfplane. How many k-sets can S have? A halving line divides S into two (n/2 - 1)-sets. If we dualize the points to lines, each k-set corresponds to a vertex in the the line arrangement below which there are exactly k lines. The set of all such points is called the kth level of the arrangement. All bounds of k-sets apply to kth levels, and vice versa.

In 1971, Lovász described a method to construct sets of points with Omega(n log n) halving lines. (This lower bound has also been attributed to Straus.) This was generalized, first by Erdõs, Lovász, Simmons, and Strauss in 1973, and later and independently by Edelsbrunner and Welzl in 1985, to an Omega(n log k) lower bound on the maximum number of k-sets. Edelsbrunner and Welzl also proved that any lower bound of the form Omega(n f(n)) for halving lines implies an Omega(n f(k)) lower bound for k-sets.

These remained the best lower bounds until 1999, when Geza Toth discovered a simple contruction of a set of n points with Omega(n2sqrt{log k}) k-sets, for any n and k<n/2. This improved an earlier (unpublished) result of Klawe, Paterson, and Pippenger on the complexity of the kth level in a pseudoline arrangement - a collection of monotone curves, every pair of which intersects exactly once, transversely.

The best known upper bounds are much larger. Lovász also proved that a set of n points in the plane has at most O(n3/2) halving lines. Erdõs, Lovász, Simmons, and Strauss generalized his proof in 1973, proving that for any integer k, an n-point set in the plane has at most O(n k1/2) k-sets. Several other proofs for this bound are known. This remained the best known upper bound until 1989, when Pach, Steiger, and Szemerédi slightly improved it to O(n k1/2 / log*n).

In 1997, Tamal Dey made the first significant dent in the k-set problem since it was first posed, reducing the upper bound to O(n k1/3). His proof is surprisingly (according to Micha Sharir, embarassingly) simple! In fact, a completely self-contained proof of his halving line bound fits on a single page.

Of course, similar questions have been posed in higher dimensions. Seidel showed that any lower bound of the form Omega(n f(n)) for halving lines in the plane implies an Omega(nd-1 f(n)) lower bound for halving hyperplanes in d dimensions. This gives us the best known lower bound Omega(nd-1 log n) on the maximum number of halving hyperplanes in a d-dimensional point set.

The best upper bound in three dimensions is O(n8/3), due to Dey and Edelsbrunner (improving earlier results of Bárány et al., Aronov et al., and Eppstein). In dimensions higher than three, the best known upper bounds are just slightly less than O(nd). Unfortunately, no generalization of Dey's proof technique to higher dimensions is known. (The obvious generalization of Dey's "convex chains" to higher dimensions are no longer necessarily convex!)

A <k-set of a point set S is a subset of size less than k that is the intersection of S with a halfspace. Despite our ignorance about k-sets, Alon and Gyõri showed that the maximum number of <k-sets in a set of n points in the plane is exactly n(k-1). (Dey uses this result in his k-set proof.) Clarkson and Shor generalized this bound to Theta(nfloor{d/2} kceiling{d/2}) in d dimensions.


References

  1. P. K. Agarwal, B. Aronov, and M. Sharir, On levels in arrangments of lines, segments, planes, and triangles, in Proc. 13th ACM Ann. Symp. Comput. Geom., 1997, pp. 30-38.

  2. N. Alon and E Gyõri, The number of small semi-spaces of a finite set of points in the plane, J. Combin. Theory Ser. A 41:154-157, 1986.

  3. K. L. Clarkson and P. Shor, Applications of random sampling, II, Discrete Comput. Geom. 4:387-421, 1989.

  4. T. K. Dey, Improved bounds for planar k-sets and related problems, to appear in Proc. 38th Ann. IEEE Symp. Found. Comput. Sci, 1997. Revised and corrected version of "Improved bounds for k-sets and k-th levels". (The higher-dimensional proofs in the original manuscript are incorrect.)

  5. T. Dey and H. Edelsbrunner, Counting triangle crossings and halving planes, Discrete Comput. Geom. 12:281-289, 1994.

  6. H. Edelsbrunner and E. Welzl, On the number of line separators of a finite set in the plane, J. Combin. Theory Ser. A 38:15-29, 1985.

  7. P. Erdõs, L. Lovász, A. Simmons, and E. G. Strauss, Dissection graphs of planar point sets, in A Survey of Combinatorial Theory, J. N. Srivastava, editor, North-Holland, 1973, pp. 139-154.

  8. M. Klawe, M. Paterson, and N. Pippenger, Inversions with n1+Omega(1+sqrt{log n}) transpositions at the median, unpublished manuscript, 1982. Reported in J. E. Goodman and R. Pollack, Allowable sequences and order types in distcrete and computational geometry, Chapter V in New Trends in Discrete and Computational Geometry, J. Pach, editor, Springer, 1993, pp. 103-134.

  9. L. Lovász, On the number of halving lines, Ann. Univ. Sci. Budapest, Eõtvõs, Sect. Math. 14:107-108, 1971.

  10. J. Pach, W. Steiger, and E. Szemerédi, An upper bound on the number of planar k-sets, Discrete Comput. Geom. 7:109-123, 1992.

  11. R. Seidel, Personal communication. Reported in H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer-Verlag, 1987.

Open Problems - Jeff Erickson (jeffe@cs.uiuc.edu) 08 Aug 1999