Counting Large Distances in Convex Polygons: A Computational Approach

Filip Morić and David Pritchard ()
Additional contact information
Filip Morić: Ecole Polytechnique Fédérale de Lausanne, Chair of Combinatorial Geometry, EPFL SB IMB DCG, MA C1 585 (Bâtiment MA)
David Pritchard: University of Waterloo, Centre for Education in Math and Computing

A chapter in Thirty Essays on Geometric Graph Theory, 2013, pp 415-428 from Springer

Abstract: Abstract In a convex n-gon, let $${d}_{1} > {d}_{2} > \cdots $$ denote the set of all distances between pairs of vertices, and let m i be the number of pairs of vertices at distance d i from one another. Erdős, Lovász, and Vesztergombi conjectured that $$\sum\nolimits_{i\leq k}{m}_{i} \leq kn$$ . Using a new computational approach, we prove their conjecture when k ≤ 4 and n is large; we also make some progress for arbitrary k by proving that $$\sum\nolimits_{i\leq k}{m}_{i} \leq (2k - 1)n$$ . Our main approach revolves around a few known facts about distances, together with a computer program that searches all distance configurations of two disjoint convex hull intervals up to some finite size. We thereby obtain other new bounds, such as m 3 ≤ 3n∕2 for large n.

Keywords: Convex Polygon; Target Distance; Regular Polygon; Typical Step; Clockwise Order (search for similar items in EconPapers)
Date: 2013
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4614-0110-0_22

Ordering information: This item can be ordered from
http://www.springer.com/9781461401100

DOI: 10.1007/978-1-4614-0110-0_22

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().