Next: Problem 8: Linear Programming:
Up: The Open Problems Project
Previous: Problem 6: Minimum Euclidean
Problem 7: ksets
 Statement
 What is the maximum number of ksets? (Equivalently, what
is the maximum complexity of a klevel 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⊂P is a kset
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 ksets as a function of n and k
is known to be
O(nk^{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.
 Dey98

T. K. Dey.
Improved bounds on planar ksets and related problems.
Discrete Comput. Geom., 19:373382, 1998.
 MO01

J. S. B. Mitchell and Joseph O'Rourke.
Computational geometry column 42.
Internat. J. Comput. Geom. Appl., 11(5):573582, 2001.
Also in SIGACT News 32(3):6372 (2001), Issue 120.
 Tot00

Géza Toth.
Point sets with many ksets.
In Proc. 16th Annu. ACM Sympos. Comput. Geom., pages 3742,
2000.
The Open Problems Project  December 08, 2012