= Solution
Let $t$ be the maximum number of positive <Euclidean distances> from one of the $n$ points to the others. It suffices to prove the stronger <Székely distinct-distance bound>, $t\geq cn^{4/5}$. Here $n\geq2$; enlarge constants to handle bounded $n$.
First prove the <crossing lemma for multigraphs>. In an optimal drawing of a loopless <multigraph> with $v$ <vertices>, $e$ <edges> and maximum parallel multiplicity $\mu$, crossings of incident <edges> can be removed by interchanging initial segments, so each remaining crossing involves four distinct <vertices>. In each parallel class choose one of its <edges> with probability $1/\mu$ per <edge>, selecting none with the remaining probability. Independently keep each <vertex> with probability $p$. The resulting <simple graph> has expected <edge> count $p^2e/\mu$, expected <vertex> count $pv$, and expected crossings $p^4X/\mu^2$, where $X$ is the original crossing count. Deleting one <edge> per crossing and using the allowed <planar graph edge bound> yields
$$
\frac{p^4X}{\mu^2}\geq\frac{p^2e}{\mu}-3pv.
$$
If $e\geq4\mu v$, take $p=4\mu v/e$ to obtain
$$
X\geq\frac{e^3}{64\mu v^2}.
$$
The case $\mu=1$ is the ordinary <crossing lemma>.
We also need the <rich line bound>. Given $L$ <lines>, connect consecutive incidence points on each <line> by straight <edges>. This <simple graph> has at least $I-L$ <edges>, where $I$ is the total number of incidences, and at most $L^2$ crossings. The <crossing lemma> gives $I=O((nL)^{2/3}+n+L)$, proving the <Szemerédi–Trotter theorem> here rather than assuming it. For <lines> containing at least $k$ points, $I\geq kL$, and absorbing the additive $L$ term gives
$$
L_{\geq k}=O(n^2/k^3+n/k),\qquad k\geq2.
$$
For bounded $k$, counting point pairs gives the same estimate with a larger absolute constant. Grouping rich <lines> into occupancy ranges $2^jk\leq s<2^{j+1}k$ and summing the resulting geometric series proves
$$
\sum_{\ell:\,|P\cap\ell|\geq k}|P\cap\ell|
=O(n^2/k^2+n\log n).
$$
Now form the <circular-arc graph for distinct distances>. Around every point draw each positive-distance <circle> centred there; there are at most $nt$ such <circles>. A <circle> with at least three of the original points contributes one <edge> between each consecutive pair around it. Discard the <circles> with at most two points. Since the total number of centre-to-point incidences is $n(n-1)$, the remaining loopless <multigraph> has
$$
e\geq n(n-1)-2nt.
$$
Its circular-arc drawing has $O(n^2t^2)$ crossings: two distinct <circles> have at most two intersections, and small perturbations remove tangencies and multiple crossings without changing this order.
The apparent difficulty is unbounded parallel multiplicity. The <rich-bisector deletion bound> controls it. Every centre supporting an arc between fixed endpoints lies on their <perpendicular bisector>. Distinct parallel arcs come from distinct centres, since their common endpoints determine the radius once the centre is fixed. Thus multiplicity at least $k$ makes that <line> contain at least $k$ of the points. For a <line> with $s$ centres, each of its at most $st$ <circles> has at most two consecutive-point arcs symmetric about that <line>, one at each end of its diameter along the <line>. The occupancy sum above therefore bounds the number of high-multiplicity arcs by
$$
O(tn^2/k^2+tn\log n).
$$
If $t\geq n^{4/5}$ there is nothing to prove. Otherwise $t\log n=o(n)$ and $t=o(n)$. Choose $k=\lceil K\sqrt t\rceil$ with a sufficiently large absolute constant $K$. The first deletion term is at most a small fixed fraction of $n^2$ and the second is $o(n^2)$. A remaining <multigraph> therefore has $e_1\geq c_1n^2$ <edges> and multiplicity at most $k$. For large $n$, $e_1\geq4kn$, so the <crossing lemma for multigraphs> gives
$$
Cn^2t^2\geq X_1\geq\frac{e_1^3}{64kn^2}
\geq c_2\frac{n^4}{\sqrt t}.
$$
Rearranging,
$$
\boxed{t^{5/2}\geq c_3n^2,\qquad t\geq cn^{4/5}.}
$$
The whole <distinct-distance set> contains those distances from the selected point, proving the requested bound. The circular-arc method and the stronger one-point conclusion are due to https://www.cs.tau.ac.il/~michas/szekely.pdf[Székely].
Back to article page
