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

摘要

Proof: Denote by f( n) the maximum number of times the unit distance can occur 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 connecting two points of P by a straight-line segment (edge) if and only if their distance is one. Pick a point p(i) antipodal to p(1), i,e., assume that there 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-axis, and that no edge of G is parallel to the y-axis. Color any edge of G red 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 ( right) endpoint. It is easy to see that every element of P is assigned to at most 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 numbering 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 pair 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]. [References: 2]