ボロノイ図・各種グラフの説明

ボロノイ図
平面上に幾つか点が散らばっている状態を考えます。 この時、「どの点が一番近いか」で平面を分けることが出来ます。 こうして平面を分けると、亀の甲羅のような (そう見えないこともありますが) 多角形に分かれます。 これをボロノイ図と言います。 また、この多角形の辺をボロノイ辺、多角形の頂点をボロノイ点、 多角形の中をボロノイ領域と言います。 ちなみに、Voronoi 氏は19世紀のロシアの数学者です。 ボロノイ図の作成は計算幾何学の代表的問題で、 コンピューターとそれの幾何学への応用によって飛躍的に進歩しましたが、 ボロノイさんは19世紀にそれを考えていたわけです。 数学者って進んでますねえ (しばしば進みすぎますが) 。

ドロネー図
ボロノイ図で、ボロノイ辺は隣り合った2つの点を結ぶ線分の垂直2等分線になっています。 このボロノイ辺がある2点を全て結ぶと、新しい図形が現れます。 これをドロネー図と言います。 ドロネー図は一部の例外を除くと三角形になります。 この一部の例外にも辺を足して全て三角形に分けたものを、 ドロネー三角形分割と言ったりします。 ちなみに、Delaunay 氏は Voronoi 氏の後輩に当たるロシアの数学者です。

ガブリエルグラフ
ボロノイ図と同じように平面上に幾つか点が散らばっている状態を考えます。 この内2つの点を選んで間を結び、その線分が直径となるような円を描きます (薄い鉛筆書きをイメージして下さい) 。 この円の中に他の点が入っていない場合、この線分を確定します (線をペンでしっかり書いたつもりになって下さい) 。 これを全ての点の組み合わせについて行い、 (消しゴムをかけて) できた図形をガブリエルグラフと言います。

相対近傍グラフ
やっぱり平面上に幾つか点が散らばっている状態を考え、この内2つの点を選びます。 それぞれの点から、他の点までの距離を測り、大きいほうの値をそろえます。 こうして集めた距離の値が全て、選んだ2点間の距離以上の大きさだったら、 この2点を結びます (面倒ですねえ) 。 これを全ての点の組み合わせについて行い、 できた図形を相対近傍グラフと言います。

最近傍グラフ
またまた平面上に幾つか点が散らばっている状態を考えます。 ある点から見て一番近い点を探し、その点に向かって矢印を書きます (これはわかり易い) 。 これを全ての点のについて行い、できた図形を最近傍グラフと言います。 この最近傍グラフは、線に向きがあるので有向グラフと言います (アプレットでは線の向きは省略していますが) 。

最小全域木
これまた平面上に幾つか点が散らばっている状態を考えます（これで最後だ）。 この点全てを線分で繋ぎます。 この時、線分の長さの合計が最小になるような繋ぎ方を最小全域木と言います。 ちなみに、木とはグラフ理論でサイクルのできない線の繋ぎ方のことです。

上のガブリエルグラフから最小全域木までは、ドロネー図の一部になっています。 よって、ドロネー図を使って効率よく描くことができます (このアプレットではあまり賢いやり方になっていませんが) 。