Next: Problem 8: Linear Programming:
Up: The Open Problems Project
Previous: Problem 6: Minimum Euclidean
Problem 7: k-sets
- What is the maximum number of k-sets? (Equivalently, what
is the maximum complexity of a k-level in an arrangement of
- Uncertain, pending investigation.
- Partial and Related Results
- For a given set P of n points,
S⊂P is a k-set
if | S| = k and S = P∩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(nk1/3) by a recent advance of Dey [Dey98],
while the best lower bound
is only slightly superlinear [Tot00].
- combinatorial geometry; point sets
- Entry Revision History
- J. O'Rourke, 2 Aug. 2001.
T. K. Dey.
Improved bounds on planar k-sets and related problems.
Discrete Comput. Geom., 19:373-382, 1998.
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.
Point sets with many k-sets.
In Proc. 16th Annu. ACM Sympos. Comput. Geom., pages 37-42,
The Open Problems Project - December 08, 2012