Distinct-distance set ($\Delta (P)=\{|p-q|:p,q\in P\}$)

For a finite planar point set $P$, its distinct-distance set is $\Delta (P)=\{|p-q|:p,q\in P\}$. It includes zero for nonempty $P$. Its cardinality measures how many different distances the configuration determines. Ordered point pairs can be grouped according to their distance, which relates the problem to incidences between points and curves.

For a finite set of at least two points in the plane, some point determines the displayed number of different positive Euclidean distances. The circular-arc graph for distinct distances has quadratically many edges. The rich-bisector deletion bound removes high-multiplicity edges while retaining that order of growth. The crossing lemma for multigraphs then compares its lower crossing bound with the quadratic count of pairs of circles. This strengthens the corresponding bound for the whole distinct-distance set. The original result is Theorem11 of Székely's 1997 paper.

Around each of $n$ points draw its at most $t$ distinct-distance circles. On every circle containing at least three points, join cyclically consecutive points by arcs. The resulting loopless multigraph has at least $n(n-1)-2nt$ edges and a drawing with $O(n^2{t}^2)$ crossings. A pair joined by several arcs has every corresponding centre on its perpendicular bisector, which is the key to bounding multiplicity.

Every supporting centre of an arc between fixed endpoints lies on their perpendicular bisector. Multiplicity at least $k$ therefore makes that line contain at least $k$ of the original points. For each such line containing $s$ points, its $s$ centres each support at most $t$ circles; on one circle at most two consecutive-point arcs have that symmetry axis. The rich line bound summed over dyadic occupancies gives the displayed bound.

For every positive distance, draw equal-radius circles centred at the points of $P$. Their incidences between points and curves count the ordered pairs at that distance. The Szemerédi–Trotter theorem for unit circles bounds each distance class by $O(|P{|}^{4/3})$. Summing over all classes accounts for $|P|(|P|-1)$ pairs, proving $|\Delta (P)|\gtrsim |P{|}^{2/3}$.