A lower bound on the number of unit distances between the vertices of a convex polygon
Edelsbrunner H, Hajnal P. 1991. A lower bound on the number of unit distances between the vertices of a convex polygon. Journal of Combinatorial Theory Series A. 56(2), 312–316.
Journal Article
| Published
| English
Scopus indexed
Author
Edelsbrunner, HerbertISTA 
;
Hajnal, Péter
;
Hajnal, PéterAbstract
This paper proves that for every n ≥ 4 there is a convex n-gon such that the vertices of 2n - 7 vertex pairs are one unit of distance apart. This improves the previously best lower bound of ⌊ (5n - 5) 3⌋ given by Erdo{combining double acute accent}s and Moser if n ≥ 17.
Publishing Year
Date Published
1991-03-01
Journal Title
Journal of Combinatorial Theory Series A
Acknowledgement
The first author is pleased to acknowledge partial support by the Amoco Fnd. Fat. Dev. Comput. Sci. i-6-44862 and the National Science Foundation under Grant CCR-8714565.
Volume
56
Issue
2
Page
312 - 316
ISSN
eISSN
IST-REx-ID
Cite this
Edelsbrunner H, Hajnal P. A lower bound on the number of unit distances between the vertices of a convex polygon. Journal of Combinatorial Theory Series A. 1991;56(2):312-316. doi:10.1016/0097-3165(91)90042-F
Edelsbrunner, H., & Hajnal, P. (1991). A lower bound on the number of unit distances between the vertices of a convex polygon. Journal of Combinatorial Theory Series A. Elsevier. https://doi.org/10.1016/0097-3165(91)90042-F
Edelsbrunner, Herbert, and Péter Hajnal. “A Lower Bound on the Number of Unit Distances between the Vertices of a Convex Polygon.” Journal of Combinatorial Theory Series A. Elsevier, 1991. https://doi.org/10.1016/0097-3165(91)90042-F.
H. Edelsbrunner and P. Hajnal, “A lower bound on the number of unit distances between the vertices of a convex polygon,” Journal of Combinatorial Theory Series A, vol. 56, no. 2. Elsevier, pp. 312–316, 1991.
Edelsbrunner H, Hajnal P. 1991. A lower bound on the number of unit distances between the vertices of a convex polygon. Journal of Combinatorial Theory Series A. 56(2), 312–316.
Edelsbrunner, Herbert, and Péter Hajnal. “A Lower Bound on the Number of Unit Distances between the Vertices of a Convex Polygon.” Journal of Combinatorial Theory Series A, vol. 56, no. 2, Elsevier, 1991, pp. 312–16, doi:10.1016/0097-3165(91)90042-F.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Google Scholar