On Unit Distances in a Convex Polygon
Amol Aggarwal · arXiv (Cornell University) · 2010
In 1959, Erdős and Moser asked for the maximum number of unit distances that may be formed among the vertices of a convex $n$-gon; until now, the best known upper bound has been $2πn \log_2 n + O(n)$, achieved by Füredi in 1990. In this paper, we examine two properties that any convex polygon must satisfy and use them to prove several new facts related to the question posed by Erdős and Moser. In particular, we improve on Füredi's result, and instead obtain a bound of $n \log_2 n + O(n)$; we exhibit a class of `cycles' formed by unit distances that are forbidden in convex polygons; and we provide a lower bound that shows the limitations of our methods. The second result addresses a question asked by Fishburn and Reeds regarding the possible configurations of vertices that form a convex polygon.