Paperlane

no. 16 · Tuesday 17 November 2026

The Deepest Pairs of Points Are Not as Deep as Conjectured

Herbert Edelsbrunner, Alexey Garber, Morteza Saghafian and Emo Welzl

math.CO

Abstract

Given any finite set of points in $\mathbb{R}^2$, Neumann-Lara and Urrutia \cite{NLUr88} proved in 1988 that there is always a pair such that every circle through the two points encloses a positive fraction of all points. While Edelsbrunner et al.\ \cite{EHSS89} showed that the fraction is at least $\sfrac{1}{2} - \sfrac{1}{\sqrt{12}} = 0.211\ldots$, Urrutia \cite{Urr02} conjectured that the constant $\sfrac{1}{4} = 0.25$ in the upper bound proved by Hayward, Rappaport and Wenger \cite{HRW89} is best possible. We disprove this conjecture by lowering the constant to $\sfrac{3}{14} = 0.214\ldots$. The new bound also disproves a related conjecture by Ramos and Viaña \cite{RaVi09} on finite sets in convex position in $\mathbb{R}^3$. Finally, we generalize the latter extremal question to finite sets in possibly non-convex position, for which we prove the first linear lower bound, with constant $\sfrac{(2-\sqrt{2})}{6} = 0.097\ldots$.

fields
Combinatorics
pdf ↗ page arXiv:2611.19600 ↗