ボロノイ図とは

平面上に、いくつかの点が配置されている。このとき、その平面ないの点を、どの点に最も近いかによって分割してできる図を、ボロノイ (Voronoi) 図という。また、その分割のことをボロノイ分割という。図1.1にボロノイ図の例を示す。

**図1.1 ボロノイ図**

配置された点のことを母点と呼ぶ。この図での母点数は5であり、ボロノイ領域は5つに分かれている。一般的なボロノイ図では、母点数とボロノイ領域数は一致する。ボロノイ領域の境目の線をボロノイ境界と呼ぶ。また、ボロノイ境界の交点をボロノイ点と呼ぶ。

ボロノイ図の応用例

ボロノイ図の応用範囲は広く、情報処理のさまざまな分野で利用されている。

など。他にもいろいろある。

隣接するボロノイ領域の母点どうしをつなぐと、もうひとつの図形が得られる。これをドロネー (Delaunay) 図と呼ぶ。図1.2に、図1.1に対応するドロネー図を示す。

**図1.2 ドロネー図**

図1.2では、ボロノイ辺を点線で、ドロネー辺を実線で表してある。

ドロネー図に表れる線分をドロネー辺といい、多角形をドロネー多角形という。通常、ドロネー多角形は三角形となるので、ドロネー図のことをドロネー三角形分割ともいう。ドロネー多角形が三角形以外になる場合は、4つの母点が同一円周上に乗るなど、特殊なケースとなっている。

ボロノイ図とドロネー図が持つ、幾何学的な特徴には次のようなものがある。