next up previous
Next: Problem 8: Linear Programming: Up: The Open Problems Project Previous: Problem 6: Minimum Euclidean


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, SP is a k-set if | S| = k and S = PH 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].
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.



The Open Problems Project - December 08, 2012