Counting Large Distances in Convex Polygons: A Computational Approach

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.