距離の出現回数 - はむ。日記

凸包の定義

点集合Pの凸包とは、Pの点を全て含む極小の凸集合のことである。

(イメージ的にはPの各点を板に打ち付けた釘とみなした時、全ての釘を含むように外側から輪ゴムを掛けてできる凸多角形がPの凸包である。)

定理:

平面上にn個の点(n≧3) ${\displaystyle\ P_{1},P_{2},...,P_{n}}$ が与えられたとき、

${\displaystyle\ {\sqrt{n-{\frac{3}{4}}}}-{\frac{1}{2}}}$ 個以上の異なる値を持つ距離が存在する。

(証明)

Case1: ${\displaystyle\ P_{1},...,P_{n}}$ が同一直線上にある

定理の成立は明らか。

Case2:Case1以外

点集合P={ ${\displaystyle\ P_{1},P_{2},...,P_{n}}$ }の凸包をとり、必要に応じて頂点の記号を交換することにより、 ${\displaystyle\ P_{1}}$ を凸包上の1点と仮定してもよい。

このとき、凸包の頂点 ${\displaystyle\ P_{1}}$ での内角は180°未満である。

${\displaystyle\ P_{1}}$ から ${\displaystyle\ P_{2},...,P_{n}}$ へのn-1個の距離を考える。これらの距離のうち ${\displaystyle\ k}$ 種類の異なる距離 ${\displaystyle\ d_{1},...,d_{k}}$ が起き、

各 ${\displaystyle\ d_{i}}$ ( ${\displaystyle\ i=1,..,k}$ )がそれぞれ ${\displaystyle\ f_{i}}$ 回起きると仮定すると、

${\displaystyle\ n-1 = \sum_{i=1}^{k} f_{i} \ }$

が成り立つ。

${\displaystyle\ f_{i}}$ のうち一番大きな値のものを ${\displaystyle\ N}$ とすると、

${\displaystyle\ \sum_{i=1}^{k} f_{i}\ ≦kN}$ となるので、

${\displaystyle\ k≧{\frac{n-1}{N}}}$ を得る。

ここでN回起きる距離をrとし、 ${\displaystyle\ P_{1}}$ を中心とする半径rの円を

${\displaystyle\ P_{1}(r)}$ で表す。

${\displaystyle\ P_{1}(r)}$ の円周上にはN個の点が存在して、それらの点を ${\displaystyle\ Q_{1},...,Q_{N}}$ とする。頂点 ${\displaystyle\ P_{1}}$ での凸包の内角が180°未満なので、N個の点 ${\displaystyle\ Q_{1},...,Q_{N}}$ は ${\displaystyle\ P_{1}(r)}$ の半円周上にある。よって、N-1個の距離 ${\displaystyle\ Q_{1}Q_{2},...,Q_{1}Q_{N}}$ はすべて異なる。

このように{ ${\displaystyle\ d_{1},...,d_{k}}$ }と{ ${\displaystyle\ Q_{1}Q_{j}}$ }( ${\displaystyle\ j=2,..,N}$ )の2つの実数の集合を考えると、それぞれちょうど ${\displaystyle\ k(≧{\frac{n-1}{N}})}$ 個とN-1個の異なる値を含む。