Erdős Problem #96

declared status 'open'. Formalized: yes. If $n$ points in $\mathbb{R}^2$ form a convex polygon then there are $O(n)$ many pairs which are distance $1$ apart. Current best: In [Er92e] Erd\H{o}s credits the conjecture that the true upper bound is $2n$ to himself and Fishburn. F\"{u}redi [Fu90] proved an upper bound of $O(n\log n)$. The best known upper bound is$$\leq n\log_2n+4n,$$due to Aggarwal [Ag15]. [EdHa91] Edelsbrunner, Herbert and Hajnal, P\'{e}ter, A lower bound on the number of unit distances between the vertices of a convex polygon. Prize: no. Tags: convex, distances, geometry.

Notation is rendered from the stored source. The pinned checkout remains the exact record.