LetSbe a set ofnpoints in the plane. Ahalving lineis a line through two points inSthat splits the remaining points into two equal-sized subsets.How many halving lines canMore generally, aShave?k-element subset ofSis called ak-setif it is the intersection ofSwith a halfplane.How manyA halving line dividesk-sets canShave?Sinto two(n/2 - 1)-sets. If we dualize the points to lines, eachk-set corresponds to a vertex in the the line arrangement below which there are exactlyklines. The set of all such points is called thekth level of the arrangement. All bounds ofk-sets apply tokth 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 anOmega(n log k)lower bound on the maximum number ofk-sets. Edelsbrunner and Welzl also proved that any lower bound of the formOmega(n f(n))for halving lines implies anOmega(n f(k))lower bound fork-sets.These remained the best lower bounds until 1999, when Geza Toth discovered a simple contruction of a set of

npoints with Omega(n2^{sqrt{log k}})k-sets, for anynandk<n/2. This improved an earlier (unpublished) result of Klawe, Paterson, and Pippenger on the complexity of thekth level in apseudolinearrangement - 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

npoints in the plane has at mostO(nhalving lines. Erdõs, Lovász, Simmons, and Strauss generalized his proof in 1973, proving that for any integer^{3/2})k, ann-point set in the plane has at mostO(n k^{1/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 k^{1/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 toO(n k. 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.^{1/3})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 anOmega(nlower bound for halving hyperplanes in^{d-1}f(n))ddimensions. This gives us the best known lower boundOmega(non the maximum number of halving hyperplanes in a^{d-1}log n)d-dimensional point set.The best upper bound in three dimensions is

O(n, due to Dey and Edelsbrunner (improving earlier results of Bárány^{8/3})et al., Aronovet al., and Eppstein). In dimensions higher than three, the best known upper bounds are just slightly less thanO(n. 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!)^{d})A

<k-set of a point setSis a subset of size less thankthat is the intersection ofSwith a halfspace. Despite our ignorance aboutk-sets, Alon and Gyõri showed that the maximum number of<k-sets in a set ofnpoints in the plane is exactlyn(k-1). (Dey uses this result in hisk-set proof.) Clarkson and Shor generalized this bound toTheta(nin^{floor{d/2}}k^{ceiling{d/2}})ddimensions.

## References

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

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

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

- 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 fork-sets andk-th levels". (The higher-dimensional proofs in the original manuscript are incorrect.)

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

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

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

- M. Klawe, M. Paterson, and N. Pippenger, Inversions with
ntranspositions 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.^{1+Omega(1+sqrt{log n})}

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

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

- 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