図形の凸性とボロノイ図

図形の凸性

関数のグラフみたいな感じで、"図形"にも"凸"という概念があります。

(b)は凹って感じで、(a)は凸って感じですね。
ちゃんとした定義を述べておきます。
[定義]図形の中の任意の２点を結ぶ線分を描く。その線分が図形の外側にはみ出していなければ図形は凸(convex)であるという。

さて、じゃあ(b)を"凸"にする場合にはどうしたらいいでしょうか。
要するにへこんだ部分を埋め立てればいいので、例えば破線のような直線を描くと凸になりそうですね。
別にこの線のひきかたは色々あるんですが、「大きさを最小に」しようと思うとこのように直線で引くのがベストです。
こうして新しくできた図形の事を凸包というのですが、やっぱりちゃんとした定義を下に書いておきます。
[定義]ある凸とは限らない図形Xがある。このXを内包しつつ凸であるような最も小さい図形を凸包(convex hull)という。

ボロノイ図とは？

(以下で使用する画像はwikipediaより引用・改変しています。3次利用に関しましてはリンク先の説明に従ってください。)

真っ黒な板の上にぽつぽつと点が乗っかっています。ボロノイ図は一定の法則に従ってこれらの点から図形を作り出すものを言います。
ちなみに上のような点のことを、ボロノイ図を作り出す母なる点ということで母点(generator)と言います。

ここで母点が色々な色を持った「繁殖速度の同じ」菌であるとしましょう。
しばらくこの菌を寝かせておくと同心円状に菌が繁殖していき、お隣の母点にお住いの菌とどこかでぶつかるはずです。
そのぶつかったところは、繁殖速度が同じという仮定から、２つの母点の距離がそれぞれ同じでなければなりません。
さて、このようにした繁殖結果は以下のようになりました。

ここでカラーリングにはどんな意味があるか考えましょう。
例えば赤のカラーリングというのは、「赤の菌の繁殖が最も早く到達する」地点です。言い換えれば、「他の母点と比較して、赤の菌が乗っている母点Sが最も近い」と言えます。
このような領域の事をSのボロノイ領域もしくは勢力圏といいます。

また、母点との距離が等しい ―勢力の拮抗している― 直線と点のことをそれぞれボロノイ辺・ボロノイ点と言います。この２つの要素だけを抽出してみます。

ボロノイ点は言い換えるならば３つの母点の外心、ボロノイ辺は２つの母点の垂直二等分線となっています。

さらに当たり前と言えば当たり前ですが、この外心円の中には他の母点は含まれません。
もし他の母点が含まれていればその点の方がボロネイ点に近くなってしまいますからね。
このような性質は空円性(empty-circle property)と言います。

退化とは？？

ある点Pがドロノイ線の点であるための条件というのは、その周囲がP1とP2の勢力圏であったとすると
$d(P,P_1)=d(P,P_2)$
という1つの条件となる(dはユークリッド距離)。ここで2次元平面に1つの条件が与えられたので、"一般的には"2次元から1次元下がって線になる。

では、ドロノイ点はどうだろうか。点になっているということは次元が2つ下がったことを意味する。つまり条件式が2つ存在していると考えるのが普通であるので
$d(P,P_1)=d(P,P_2) d(P,P_1)=d(P,P_3)$
といったように「3つの母点とそれぞれの距離が一緒である点」と考えられる。
このような母点を非退化しているという。

以上の話は次元と条件式の関係から見た"一般的な話"だった。
しかし、素朴に考えて、例えば母点が正方形の頂点上に存在していたとしたらどうだろうか？