2015/07/28

ボロノイ図とその3つの性質

分野: グラフ理論  レベル: マニアック

点(母点)がいくつか与えられたとき,どの点に一番近いかによって平面を分割したものをボロノイ図(Voronoi diagram)と言う。

三つ目の性質&その証明が美しいのでおすすめです。

ボロノイ図の例

図は母点の数が $6$ 個であるボロノイ図の例です(フリーハンドで書いたので誤差はご勘弁ください)。辺は垂直二等分線の一部,点は外心になります。

ボロノイ図の例

ボロノイ図は各母点の勢力範囲を表すものだと解釈できます。実際にいろいろな問題に応用されています。

今回は平面+通常の距離(ユークリッド距離)の場合のみを考えますが,別の空間や距離でボロノイ図を考えることもできます。

ボロノイ図は凸

性質1.ボロノイ図の各領域は凸である。

ここで,領域 $S$ が凸とは,二点 $A,B\in S$ なら線分 $AB$ が $S$ に含まれることを言います。へこんでいないという意味です。

証明

母点 $P_1$ のボロノイ領域に属する二点 $A,B$ を取ってくる。
また,他の母点の一つを $P_i$ とする。

「 $P_i$ よりも $P_1$ に近い点の集合」は半平面をなす(境界は $P_1P_i$ の垂直二等分線)。この半平面に $A,B$ が属しているので,線分 $AB$ 全体もこの半平面に属す。

つまり.線分 $AB$ 上の任意の点は「 $P_i$ よりも $P_1$ に近い」を満たす。以上の議論は各 $i$ について成立するので,線分 $AB$ は $P_1$ のボロノイ領域に含まれる。

ボロノイ図の空円性

以下,ボロノイ図の辺をボロノイ辺,頂点をボロノイ点と言います。

ボロノイ点には三本以上のボロノイ辺が接続しています(もし二本しか接続していないと隣接するボロノイ領域のいずれかが凸でなくなる)。

性質2.ボロノイ点を中心とし,その点に隣接する領域(三つ以上ある)の母点を通る円は,(内部に)他の母点を含まない。

ボロノイ図の空円性

証明

背理法で証明する。ボロノイ点を $V$,その点に隣接する領域の母点の一つを $P$ とする。 $V$ を中心とし $VP$ を半径とする円の中に別の母点 $Q$ が含まれるとすると,$VP > VQ$ となる。

よって,$V$ のすぐ近くの点は $P$ よりも $Q$ が近くなるため,$V$ に隣接する領域の母点の一つが $P$ であることに矛盾。

ボロノイ点,ボロノイ辺の数

少し難しいですが,一番おもしろいです!

性質3.母点の数を $n$,ボロノイ点の数を $v$,ボロノイ辺の数を $e$ とすると,$v\leq 2n-2,\:e\leq 3n-3$

ボロノイ図の点や辺の数は母点の数の数倍でおさえられる,つまりボロノイ図はそんなに複雑にならないということですね。証明には平面グラフにおけるオイラーの多面体定理を用います。

証明

ボロノイ図を十分大きな円でカットした平面グラフ $G$ を考える。 $G$ の頂点数を $V$,枝数を $E$,面の数を $F$ とおくと,オイラーの多面体定理から $V-E+F=2$ である。

ボロノイ図の点の数

円周上の点の個数を $k$ とすると,$V=v+k$,$E=e+k$ である。また,一番外側の領域も面数 $F$ にカウントされているので $F=n+1$ である。
以上より,$(v+k)-(e+k)+(n+1)=2$,つまり $v-e+n=1$  

また,各ボロノイ点には三本以上の枝が接続しているので,$3v\leq 2e$
ただし,ボロノイ辺は一つまたは二つのボロノイ点に接続する(無限遠に伸びるものは一つの点のみと接続)ことを使った。

以上二つの式から $e$ を消去すると $v\leq 2n-2$
$v$ を消去すると,$e\leq 3n-3$ を得る。

性質3の証明は,データ構造とアルゴリズム(杉原厚吉著)という本を参考にしました。

性質3の証明で $k$ が消えるとこが素晴らしいですね!
分野: グラフ理論  レベル: マニアック