ボロノイ図とドロネー図
とある本に出てきて、もしかしたら後で道具として使えそうな気がしたのでメモしておきます。
ボロノイ図
ある距離空間上の任意の位置に配置された複数個の点 (母点) に対して、同一距離空間上の他の点がどの母点に近いかによって領域分割された図。
ドロネー図
隣接するボロノイ領域の母点同士をつなぐ線分によって領域分割された図。
ボロノイ図については、1908年にロシアの数学者 Georgy Fedoseevich Voronoi が n 次元の場合の研究をしました。応用には、携帯電話の基地局探索、降水量予測、学区設定などがあります。ドロネー図については、Voronoi の後輩であるロシアの数学者 Delaunay が考案しました。応用には、ポリゴン生成のようなモデリングなどがあります。サッカーのシミュレーションやコンピュータ囲碁にもこういった図を適用すると面白そうです (両者の分野ともに、実際に適用している研究は既に有るようです)。
Wikipedia のリンクをメモしておきます。