Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647079 | Discrete Mathematics | 2015 | 5 Pages |
Abstract
In 1959, ErdÅs and Moser asked for the maximum number of unit distances that may occur among the vertices of a convex n-gon. Until now, the best known upper bound has been 2Ïnlog2n+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 facts related to the above question. In particular, we improve upon Füredi's result, obtaining a bound of nlog2n+O(n); we exhibit a new 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 answers a question of Fishburn and Reeds in the negative.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Amol Aggarwal,