On Distinct Distances from a Vertex of a Convex Polygon

Adrian Dumitrescu
Discrete and Computational Geometry
Volume 36, Number 4 / December, 2006
Pages 503-509
http://dx.doi.org/10.1007/s00454-006-1262-y

SoCG2004の特集号から．

平面上で凸の位置にあるn個の点を考える．
その中のある1点から他の点からの距離を全部考えて，その中のいくつが異なるか見てみる．
このとき，必ずある点からの相違距離の数がn/3の切り上げ以上になることを1952年にMoserは示した．
Erdosはこの数字 (下界) をn/2の切り上げにできると予想している．
(これはbest possible．)
この論文では，Moserの下界を(13n-6)/36の切り上げに改善している．

証明はMoserの証明と同様に進行するが，途中で点集合が定める正三角形の数を評価する部分がある．
この論文はその部分を改善することによって，全体を改善したことになっている．