Maximum number of k-sets
Let $P$ be a set of $n$ points. A subset $S \subset P$ is a $k$-set of $P$ if $|S| = k$ and $S = P \cap H$ for some open halfspace $H$.
The question is unsettled even in the plane. There Dey proved that a set of $n$ points has $O(nk^{1/3})$ $k$-sets, while the best lower bound, due to Tóth, exceeds linear only slightly. For the halving case, $n$ even and $k = (n-2)/2$, Nivasch improved Tóth's construction, raising the constant in the exponent.
Problem. How many $k$-sets can a set of $n$ points have at most? Equivalently, how large can the combinatorial complexity of a $k$-level in an arrangement of $n$ hyperplanes be?
Source: Origin uncertain; Problem 7 of The Open Problems Project (Demaine, Mitchell and O'Rourke).
Imported from topp.openproblem.net.
Classification
- Primary
- CO — Combinatorics
- Secondary
- MG
- Keywords
- halving lines, k-sets, The Open Problems Project
References
@article{dey1998,
author = {Dey, T. K.},
title = {Improved bounds on planar $k$-sets and related problems},
journal = {Discrete Comput. Geom.},
volume = {19},
year = {1998},
pages = {373--382},
}
@inproceedings{toth2000,
author = {T{\'o}th, G{\'e}za},
title = {Point sets with many $k$-sets},
booktitle = {Proc. 16th Annu. ACM Sympos. Comput. Geom.},
year = {2000},
pages = {37--42},
}
@inproceedings{nivasch2008,
author = {Nivasch, Gabriel},
title = {An improved, simple construction of many halving edges},
booktitle = {Proc. Snowbird Conference Discrete and Computational Geometry: Twenty Years Later},
editor = {Goodman, J. E. and Pach, J. and Pollack, R.},
series = {Contemporary Mathematics},
volume = {453},
publisher = {American Mathematical Society},
address = {Providence, RI},
year = {2008},
pages = {299--305},
url = {https://rangevoting.org/many_halving_edges.pdf},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-01070, "Maximum number of k-sets", clopen.solutions.