[Thm] 平面上に()個の点が与えられたとき、最短距離は個より多くは起こりえない。 (証明) 最短距離をとおく。 点の個数のグラフGを次のように定める。 「Gの頂点集合をとする。また2点,間の距離がのときに限りそれら2点を結ぶ。この操作により得られた線分の…

凸包の定義 点集合Pの凸包とは、Pの点を全て含む極小の凸集合のことである。 (イメージ的にはPの各点を板に打ち付けた釘とみなした時、全ての釘を含むように外側から輪ゴムを掛けてできる凸多角形がPの凸包である。) 定理: 平面上にn個の点(n≧3)が与えられた…