The Maximum Number of Times the Same Distance Can Occur among the Vertices of a Convex n-gon Is O(n log n)
✍ Scribed by Peter Braß; János Pach
- Publisher
- Elsevier Science
- Year
- 2001
- Tongue
- English
- Weight
- 70 KB
- Volume
- 94
- Category
- Article
- ISSN
- 0097-3165
No coin nor oath required. For personal study only.
✦ Synopsis
Proof. Denote by f (n) the maximum number of times the unit distance can occur among n points in convex position in 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, l and l$, 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 l and l$ 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.