**Next:** Problem 8: Linear Programming: Strongly Polynomial?

**Previous:** Problem 6: Minimum Euclidean Matching in 2D

- 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
- Categories
combinatorial geometry; point sets

- Entry Revision History
J. O’Rourke, 2 Aug. 2001.

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