ボロノイ線図

離散的な点の集合を表すボロノイ線図では、それらの点のまわりの空間を影響範囲に分解します。この分解は、影響範囲内にある任意の点が他の点よりも当該点に近いという性質をもっています。影響範囲はボロノイ領域と呼ばれ、ボロノイ領域が合わさってボロノイ線図を形成します。ボロノイ線図は N 次元の幾何構成ですが、実際の用途は 2 次元および 3 次元空間であることがほとんどです。

次のいずれかの手法を使用して、ボロノイ線図のトポロジを計算します。

どちらの手法でも、ボロノイ線図のトポロジを行列形式で表します。このデータ構造体の詳細については、三角形分割を参照してください。