The maximum number of times the same distance can occur among the verticesof a convex n-gon Is O(n log n)

Proof: Denote by f( n) the maximum number of times the unit distance can oc cur among n points ill convex position ill the plane. Let p(1), p(2),...., p(n), in this cyclic order, be the vertices of a convex polygon, for which the maximum is attained. Let G denote the geometric graph obtained by conne cting two points of P by a straight-line segment (edge) if and only if thei r distance is one. Pick a point p(i) antipodal to p(1), i,e., assume that t here are two parallel lines, t and t', passing through p(1), and p(i), resp ., such that all elements of P are in the strip between them. We claim that all but at most 2n edges of G cross p(1) p(i). To verify this . suppose without loss of generality that t and t' are parallel to the x-ax is, and that no edge of G is parallel to the y-axis. Color any edge of G re d if its slope is positive and blue otherwise. Assign every red edge lying in the closed half-plane to the left (right) of p(1) p(i) to its left ( rig ht) endpoint. It is easy to see that every element of P is assigned to at m ost one red edge. Therefore, the number of red edges not crossing p(1) p(i) is at most n. The same is true for the blue edges, which proves the claim. We can assume without loss of generality that i > n/2, otherwise the number ing of the vertices can be reversed. Take a point p(j) antipodal to p([i/2] ). As above, there are at most 2n edges of G, which do not cross p([i/2]) p (j). Every edge of G, crossing both p1 pi and p([i/2]) p(j), connects a pai r of points in P-1:= {p(2), p(3),.. P[i/2]-1}boolean OR { Pi+1, Pi+2,..., Pj-1} or in P-2 :={p([i/2]+1), p([i/2]+2),..., Pi-1} boolean OR {Pj+1, Pj+2, ..., P-n}. Thus, we have f(n) = \ E(G)\ less than or equal to f( \ P-1\) + f( \ P-2 \) + 4n. Using the facts that \P-1\ + \P-2\ = n - 4 and min (\P-1\, \P-2\ ) greater than or equal to (n-7/)(4), the theorem follows by induction. It is an exciting open problem to decide whether f(n)= O(n) holds. The best known general lower bound, f(n) greater than or equal to 2n - 7, is due to Edelsbrunner and Hajnal [EH].