Erdős Problem #93 — Distances Determined by Convex Point Sets

Erdős posed the conjecture in 1946, asserting that the vertices of every convex $n$-gon determine at least $\lfloor n/2\rfloor$ distinct distances, with equality for a regular $n$-gon. Altman proved this all-pairs statement in 1963 (and is also credited with a 1972 treatment).

Known results

• Altman, 1963: every set of $n$ points in convex position determines at least $\lfloor n/2\rfloor$ distinct pairwise distances; regular $n$-gons attain the bound. Fishburn later classified the complementary even-$n$ equality case.

The stronger one-vertex conjecture remains open

Erdős also conjectured that some vertex alone determines at least $\lfloor n/2\rfloor$ distances. The best reported lower bound is $\left(\frac{13}{36}+\frac{1}{22701}\right)n-O(1)$, due to Nivasch, Pach, Pinchasi, and Zerbib, improving Dumitrescu’s 2006 bound.

Current status (as of March 2026): The stated all-pairs problem is resolved by Altman; only the stronger one-vertex version remains open.