The Open Problems Project

Next: Problem 8: Linear Programming: Strongly Polynomial?

Previous: Problem 6: Minimum Euclidean Matching in 2D

Problem 7: $k$-sets

Statement

What is the maximum number of $k$-sets? (Equivalently, what is the maximum complexity of a $k$-level in an arrangement of hyperplanes?)

Origin

Uncertain, pending investigation.

Status/Conjectures

Open.

Partial and Related Results

For a given set $P$ of $n$ points, $S\subset P$ is a $k$-set if $|S|=k$ and $S=P\cap H$ for some open halfspace $H$. Even for points in two dimensions the problem remains open: The maximum number of $k$-sets as a function of $n$ and $k$ is known to be $O(n k^{1/3})$ by a recent advance of Dey [Dey98], while the best lower bound is only slightly superlinear [Tot00].

Appearances

[MO01]

Categories

combinatorial geometry; point sets

Entry Revision History

J. O’Rourke, 2 Aug. 2001.

Bibliography

[Dey98]

T. K. Dey. Improved bounds on planar $k$-sets and related problems. Discrete Comput. Geom., 19:373–382, 1998.

[MO01]

J. S. B. Mitchell and Joseph O’Rourke. Computational geometry column 42. Internat. J. Comput. Geom. Appl., 11(5):573–582, 2001. Also in SIGACT News 32(3):63-72 (2001), Issue 120.

[Tot00]

Géza Toth. Point sets with many $k$-sets. In Proc. 16th Annu. ACM Sympos. Comput. Geom., pages 37–42, 2000.