The k-set problem: how many halving lines can n points have?

Take $n$ points in the plane. How many ways can a straight line cut off exactly $k$ of them? This basic counting question, which also governs the complexity of levels in line arrangements and of several geometric algorithms, has resisted fifty years of work: the best upper and lower bounds are still far apart.

Problem

Let $P$ be a set of $n$ points in the plane, no three on a line. A subset $S\subseteq P$ is a $k$-set if $|S|=k$ and $S=P\cap H$ for some open half-plane $H$. Let $e_k(n)$ be the largest number of $k$-sets that a set of $n$ points can have. For even $n$, a halving line of $P$ is a line through two points of $P$ with exactly $(n-2)/2$ points of $P$ on each side; let $h(n)$ be the largest number of halving lines of an $n$-point set. Halving lines are the middle case: an $n$-point set has exactly twice as many $(n/2)$-sets as halving lines.

Question. Determine the order of growth of $e_k(n)$, and in particular of $h(n)$. Erdős, Lovász, Simmons and Straus conjectured that $h(n)=O(n^{1+\varepsilon})$ for every $\varepsilon>0$.

By duality, $k$-sets correspond to vertices of the $k$-th level of an arrangement of lines, so the same bounds govern the complexity of levels.

Background

Lovász (1971) proved the first upper bound, $O(n^{3/2})$ halving lines, and Erdős, Lovász, Simmons and Straus (1973) extended the question to $k$-sets [1]. The problem is Problem 7 of The Open Problems Project, in its original list of thirty. It also has higher-dimensional versions, where the gaps between the bounds are wider still.

What is known

• Upper bounds. $e_k(n)=O(n\sqrt{k})$ (Erdős, Lovász, Simmons and Straus, 1973) [1], improved by a $\log^* n$ factor by Pach, Steiger and Szemerédi (1992). Dey (1998) proved $e_k(n)=O(nk^{1/3})$, hence $h(n)=O(n^{4/3})$ [2].
• Lower bounds. $\Omega(n\log k)$ $k$-sets (Erdős, Lovász, Simmons and Straus; Edelsbrunner and Welzl). Tóth (2001) constructed sets with $n\,e^{\Omega(\sqrt{\log k})}$ $k$-sets [3]. For halving lines, Nivasch (2008) improved the constant in the exponent, obtaining $\Omega\big(n\,e^{\sqrt{\ln 4}\sqrt{\ln n}}/\sqrt{\ln n}\big)$ [4].
• Small cases. The exact value of $h(n)$ is known for every $n\le 27$ (Ábrego, Cetina, Fernández-Merchant, Leaños and Salazar, 2012) [5].

What would count as progress

• An upper bound $h(n)=O(n^{4/3-\delta})$ for some explicit $\delta>0$, or a lower-bound construction with $n\,e^{c\sqrt{\ln n}}$ halving lines for a constant $c$ larger than $\sqrt{\ln 4}$, or with $n^{1+\delta}$ halving lines.
• Exact values of $h(n)$ for $n>27$. A point set certifies a lower bound and can be checked by counting its halving lines in $O(n^2\log n)$ time; an upper bound needs a proof.
• Better bounds for $e_k(n)$ in a range of $k$, or for halving planes in three dimensions.

References

1. P. Erdős, L. Lovász, A. Simmons and E. G. Straus, Dissection graphs of planar point sets, in A Survey of Combinatorial Theory, North-Holland (1973), 139–149. doi:10.1016/B978-0-7204-2262-7.50018-1
2. T. K. Dey, Improved bounds for planar $k$-sets and related problems, Discrete Comput. Geom. 19 (1998), 373–382. doi:10.1007/PL00009354
3. G. Tóth, Point sets with many $k$-sets, Discrete Comput. Geom. 26 (2001), 187–194. doi:10.1007/s004540010022
4. G. Nivasch, An improved, simple construction of many halving edges, Contemp. Math. 453 (2008), 299–305. doi:10.1090/conm/453/08804
5. B. M. Ábrego, M. Cetina, S. Fernández-Merchant, J. Leaños and G. Salazar, On $(\le k)$-edges, crossings, and halving lines of geometric drawings of $K_n$, Discrete Comput. Geom. 48 (2012), 192–215. doi:10.1007/s00454-012-9403-y

Source

Imported from The Open Problems Project, Problem 7, curated by Erik D. Demaine, Joseph S. B. Mitchell and Joseph O'Rourke. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.