# 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](https://doi.org/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](https://doi.org/10.1007/PL00009354)
3. G. Tóth, Point sets with many $k$-sets, *Discrete Comput. Geom.* 26 (2001), 187–194. [doi:10.1007/s004540010022](https://doi.org/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](https://doi.org/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](https://doi.org/10.1007/s00454-012-9403-y)

## Source

Imported from [The Open Problems Project, Problem 7](https://topp.openproblem.net/p7), 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.