The near-linear bound for planar halving lines
Let $n \ge 2$ be even and let $P \subset \mathbb{R}^2$ be a set of $n$ points, no three collinear. A halving line of $P$ is a line through two points of $P$ with exactly $(n-2)/2$ of the remaining points in each of its open half-planes. Let $h(P)$ be the number of halving lines of $P$, and $h(n)$ the maximum of $h(P)$ over all such $P$. Erdős, Lovász, Simmons and Straus proved $h(n) < n^{3/2}$ and constructed sets with more than $\frac{n}{4} \log_2 \frac{n}{3}$ halving lines (1973). Tóth constructed sets with $n e^{c\sqrt{\log n}}$ halving lines for some constant $c > 0$ (2001), and Dey proved $h(n) = O(n^{4/3})$ (1998).
Problem. Is it true that for every $\varepsilon > 0$ there is a constant $C_\varepsilon > 0$, independent of $n$ and $P$, such that $h(n) \le C_\varepsilon n^{1+\varepsilon}$ for every even $n \ge 2$?
Source: Erdős, Lovász, Simmons and Straus (1973), Conjecture 5.2, as e_n = o(n^{1+ε}) for every ε > 0, where e_n is the largest number of halving lines of 2n points in general position.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Secondary
- MG
- Keywords
- AIM Open Applied Problems, halving lines, k-sets, planar point sets
References
@incollection{erdos1973,
author = {Erd{\H{o}}s, P. and Lov{\'a}sz, L. and Simmons, A. and Straus, E. G.},
title = {Dissection graphs of planar point sets},
booktitle = {A Survey of Combinatorial Theory},
editor = {Srivastava, J. N. and others},
publisher = {North-Holland},
address = {Amsterdam},
year = {1973},
pages = {139--149},
doi = {10.1016/B978-0-7204-2262-7.50018-1},
}
@article{toth2001,
author = {T{\'o}th, G{\'e}za},
title = {Point sets with many $k$-sets},
journal = {Discrete Comput. Geom.},
volume = {26},
number = {2},
year = {2001},
pages = {187--194},
doi = {10.1007/s004540010022},
}
@article{dey1998,
author = {Dey, T. K.},
title = {Improved bounds for planar $k$-sets and related problems},
journal = {Discrete Comput. Geom.},
volume = {19},
number = {3},
year = {1998},
pages = {373--382},
doi = {10.1007/PL00009354},
}
@misc{aim-planar-halving-lines,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{The near-linear bound for planar halving lines}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/346-planar-halving-lines.md},
note = {Entry 346 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00547, "The near-linear bound for planar halving lines", clopen.solutions.