Distinct distances from a vertex of a convex polygon

In a regular $n$-gon, each vertex sees only $\lfloor n/2\rfloor$ different distances to the other vertices. Erdős conjectured that no convex polygon does better: some vertex always sees at least $\lfloor n/2\rfloor$ distinct distances. The best proven bound has crept up from $n/3$ to about $0.36n$, and since the conjecture is about finite configurations, a counterexample would be a concrete polygon.

Problem

Let $p_1,\dots,p_n$ be the vertices of a convex polygon in the plane. Is there always a vertex $p_i$ such that the distances $\lvert p_i-p_j\rvert$, $j\neq i$, take at least $\lfloor n/2\rfloor$ distinct values?

Background

Erdős raised this in his 1946 paper on distances, together with a stronger conjecture that would imply it: that some vertex has no three other vertices at the same distance from it. That stronger statement is false: Danzer found a convex 9-gon in which every vertex has three other vertices at a common distance, and it is now known that for large $n$ a convex $n$-gon can have $\gg\log\log n$ vertices at distance $1$ from every vertex (see problem 97). The weaker statement about $\lfloor n/2\rfloor$ distances remains open. The regular polygon shows that $\lfloor n/2\rfloor$ would be best possible. Erdős also conjectured that on every convex curve there is a point $p$ such that every circle centred at $p$ meets the curve at most twice; Bárány and Roldán-Pensado (2013) observed that the boundary of an acute triangle is a counterexample, and proved a version with a constant depending on the curve.

What is known

Let $f(n)$ be the number of distinct distances that some vertex of every convex $n$-gon is guaranteed to have.

• Moser (1952): $f(n)\ge\lceil n/3\rceil$.
• Erdős and Fishburn (1994): $f(n)\ge\lfloor n/3+1\rfloor$.
• Dumitrescu (2006): $f(n)\ge\lceil(13n-6)/36\rceil$.
• Nivasch, Pach, Pinchasi and Zerbib (2013): $f(n)\ge\left(\tfrac{13}{36}+\tfrac{1}{22701}\right)n-O(1)$.
• A proof claim posted in July 2026 (S. D. Kominers) refines their argument to $f(n)\ge\left(\tfrac{13}{36}+\tfrac{3}{5270}\right)n-O(1)$; it has not been refereed.

What would count as progress

• A convex polygon in which every vertex sees fewer than $\lfloor n/2\rfloor$ distinct distances, which would disprove the conjecture; for exact coordinates this is a finite check.
• A lower bound $f(n)\ge cn$ with $c$ noticeably larger than $13/36$, or a proof of the conjecture.
• Exhaustive or certified searches over small $n$, for example using the algebraic constraints that equal distances impose.
• A formal proof against the Lean statement in formal-conjectures.

References

1. L. Moser, On the different distances determined by $n$ points, Amer. Math. Monthly 59 (1952), 85–91. doi:10.1080/00029890.1952.11988075
2. P. Erdős and P. Fishburn, A postscript on distances in convex $n$-gons, Discrete Comput. Geom. 11 (1994), 111–117. doi:10.1007/BF02573998
3. A. Dumitrescu, On distinct distances from a vertex of a convex polygon, Discrete Comput. Geom. 36 (2006), 503–509. doi:10.1007/s00454-006-1262-y
4. G. Nivasch, J. Pach, R. Pinchasi and S. Zerbib, The number of distinct distances from a vertex of a convex polygon, J. Comput. Geom. 4 (2013), 1–12. arXiv:1207.1266
5. I. Bárány and E. Roldán-Pensado, A question from a famous paper of Erdős, Discrete Comput. Geom. 50 (2013), 253–261. doi:10.1007/s00454-013-9507-z

Source

Imported from Erdős Problems 982, curated by Thomas Bloom. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.