Quadratically Many Essentially Different Lines in Dense Point Sets

Definitions and mathematical statement

Let $n\ge 2$ and let $P\subset{\mathbb{R}}^2$ be a set of $n$ points. Write \[ \operatorname{sep}(P)=\min_{p\ne q\in P}\|p-q\|_2, \qquad \operatorname{diam}(P)=\max_{p,q\in P}\|p-q\|_2, \] and let $\mathcal L(P)$ be the set of distinct affine lines through pairs of distinct points of $P$. For an unoriented line $\ell$, let $\theta_\ell\in[0,\pi)$ represent its direction, with angles measured in radians. Define the angular distance between two line directions by \[ \delta(\ell,m)=\min\{|\theta_\ell-\theta_m|,\pi-|\theta_\ell-\theta_m|\}. \] For $r>0$, define the closed Euclidean neighborhood \[ N_r(\ell)=\{x\in{\mathbb{R}}^2:\operatorname{dist}(x,\ell)\le r\}. \] Under this neighborhood convention, call two distinct lines $\ell,m$ essentially different at size $n$ if \[ \delta(\ell,m)\ge \frac1n \quad\text{or}\quad N_{1/\sqrt n}(\ell)\cap N_{1/\sqrt n}(m)\cap\operatorname{conv}(P)=\varnothing. \] Here $\operatorname{conv}(P)$ is the convex hull of $P$.

The usual uniform interpretation of the supplied asymptotic question is the following. For every fixed $C>0$, do there exist constants $c(C)>0$ and $n_0(C)\ge2$ such that, for every integer $n\ge n_0(C)$ and every such $P$ satisfying \[ \operatorname{sep}(P)=1, \qquad \operatorname{diam}(P)\le C\sqrt n, \] there is a family $\mathcal F\subseteq\mathcal L(P)$ with \[ |\mathcal F|\ge c(C)n^2 \] whose distinct members are pairwise essentially different?

The supplied record does not specify whether neighborhoods are open or closed; the display above uses closed neighborhoods as an explicit provisional convention. Replacing $\le r$ by $<r$ gives the other boundary interpretation, which remains unresolved by the supplied evidence. The dependence of the lower-bound constant and threshold on the fixed diameter constant is also an explicit interpretation of the asymptotic notation, rather than an additional source-verified assertion.

Short English statement

Must every planar set of $n$ points with minimum pairwise distance exactly $1$ and diameter at most a fixed multiple of $\sqrt n$ determine a quadratic-size family of lines such that each pair either differs in direction by at least $1/n$, or has disjoint $1/\sqrt n$-neighborhoods within the convex hull? The neighborhood boundary convention and the intended uniformity of the asymptotic constants require review.

Sources

• Local UnsolvedMath registry, permanent ID $30003475$, source problem code catalogue entry, title "Quadratically Many Essentially Different Lines in Dense Point Sets," in the Oberwolfach Reports Open Problems collection. No individual proposer is identified; the supplied proposed year is $2017$.
• Supplied report citation: Discrete Geometry (2018), Oberwolfach Reports, DOI 10.4171/owr/2017/19, pp. 1135--1205. https://doi.org/10.4171/owr/2017/19. This is the supplied authoritative provenance; it has not been independently consulted for this draft.
• Supplied literature reference labeled "Pach Rubin and Tardos on crossing segments": https://doi.org/10.1016/j.aim.2021.107779.
• Supplied literature reference labeled "original OWR report": https://doi.org/10.4171/owr/2017/19.
• Literature assessment dated exactly 2026-08-21: the supplied curation labels the record partially solved and states that three density conjectures remain open in their stated sharp forms, with $n^{2-\varepsilon}$ line bounds and $n^{1-\varepsilon}$ crossing bounds providing partial progress. This is supplied dated curation derived from the OWR material, not an independently verified literature assessment. The record requests independent verification of time-sensitive status and cited claims.
• The registry labels the statement corrected_verified and reports that the official report was checked directly to restore definitions and remove source-dependent wording. This describes the supplied registry's verification claim, not verification performed for this draft.