ボロノイ図

ボロノイ図は、母点と呼ばれる点の集まりに平面を分け与えます。各母点の領域は、その母点に、ほかのどの母点と比べても同じかそれ以上に近い点の集まりです。画面は平面の一部をのぞく窓で、領域内の濃淡は見やすくするためだけのものです。青いプローブは、最も近い母点まで届く空円の中心です。ここでは母点を動かして隣の領域の変化を見たり、各母点から領域を成長させたり、ドロネー三角形分割を表示したり、母点を均等に広げて蜂の巣に近づけたりできます。

母点$p$までの距離が別の母点$q$までの距離以下となる点は、$pq$の垂直二等分線を境界とする半平面を作ります。$p$の領域は、ほかの母点ごとに1つあるこれらの半平面の共通部分なので凸です。二等分線のうち、辺になるのは一部だけです。$p$の領域と辺を共有する領域の母点が隣接する母点で、残りの半平面はすでに領域全体を含んでいます。枠は窓を区切るだけです。領域が無限遠まで伸びるのは、その母点が全母点の凸包の境界上にある場合、かつその場合に限ります。

3つ以上の領域が集まる頂点は、それぞれの母点から等距離にあるので、母点を通る円の中心です。その円の内部には母点がありません。もしあれば、その母点のほうが頂点に近く、頂点はそちらの領域に属するはずです。通常は1つの頂点でちょうど3つの領域が集まります。正方格子のように、ちょうど4つの母点が1つの空円上にあると4領域が集まりますが、無作為に散らした母点ではほとんど起こりません。

成長では、各母点から円盤が同じ速さで広がります。各点には最も近い母点から最初に届くので、前線はちょうど領域の辺で出会います。小さな表示は、同じ成長を横から見せます。各位置で、最も近い母点までの距離を高さにします。これは、母点に立つ円錐$z = |x - s|$のうち最も低い高さです。尾根が辺に対応し、成長は水位の上昇に対応します。最後に水に沈む場所は枠内の地形の最高点であり、中心を枠内に置ける最大空円の中心です。

三角形分割は、領域が辺を共有する母点同士を結びます。正方格子のように4つ以上の母点が同じ空円上にある場合は、破線の対角線も加えます。すべての母点が一直線上にある場合を除けば、結果はドロネー三角形分割です。各三角形の外接円は、ボロノイ図の頂点を中心とする空円です。

均等化は、枠で切り取った各領域の重心へ母点を動かし、領域を作り直す操作を繰り返します。これがロイド法です。小さなグラフは、枠内の点から最も近い母点までの距離の二乗平均を、母点1つ当たりの枠の面積で割った値を示します。どの回でも、この値が増えることはありません。母点が固定なら最寄りの母点に割り当てた領域が、領域が固定なら重心が、この値を最小にします。蜂の巣の線は下限で、同じ大きさの正六角形の中心に母点を置いたときの値です。散らばった母点から始めると、完全な蜂の巣ではなく、近くの安定した配置で止まります。通常は五角形と七角形が隣り合って残り、結晶の転位に似た形になります。

この図は、1908年に任意の次元でこうした分割を研究したゲオルギー・ボロノイにちなんで名付けられました。三角形分割の名は、1934年にそれを記述したボリス・ドロネーに由来します。