ボロノイ図
ボロノイ図の利用例は(きちんとそれが定式化される以前も含めれば)1644年のデカルトまで遡ることができる。ディリクレは1850年に二次形式についての自身の研究において、2次元と3次元のボロノイ図を用いている。このことから、ボロノイ図にはディリクレ空間分割(英: Dirichlet tessellation)の異称もある。
ボロノイ図の名はロシア人数学者ゲオルギ・フェドセビッチ・ボロノイ (英語版)に因んだもので、彼は1908年に一般の n-次元の場合を定義、研究した。地球物理学や気象学で(降雨量測定のような)空間分布データの解析に用いられるボロノイ図は、アメリカ人気象学者アルフレッド・H・ティーセンの名前を取って、ティーセン多角形(Thiessen polygon)と呼ばれている。凝縮系物理学ではボロノイ細胞はウィグナー=サイツ単位セル(Wigner-Seitz unit cell)として知られる。運動量の逆格子から得られるボロノイ図はブリルアンゾーン(Brillouin zone)と呼ばれる。リー群における一般格子に対し、そのボロノイ細胞のことを簡単に基本領域 (fundamental domain) と呼ぶ。一般距離空間の場合には、そのボロノイ細胞のことをしばしば計量基本多項式(metric fundamental polygon)と呼ぶ。
最近点探索:与えられた点に最も近い母点を探す問題は直接的にのみならず、複雑な問題の一部分としても現れ、ボロノイ領域を応用したデータ構造を構築することで素早く探すことができる。
ロボット動作計画:障害物を避けて目的地に到達することが可能であれば、障害物を母点とするボロネイ境界上に経路をとることができる。このように空間をより低次元の骨格に置き換える手法はレトラクション・アプローチ(retraction approach)と呼ばれる。
ドロネー三角形分割:ユークリッド平面上のボロノイ図において、もしいずれの4母点も同一円上に無ければ、ボロノイ領域が辺を共有する母点同士を線分で繋ぐことで母点全体の凸包をいくつかの三角形で分割したものが得られ、この三角形分割は理論・応用の両面において興味深い性質を持つ。
補間:有限の点集合 P 上の値のみがわかっている関数のある点 x での値を推測する方法の一つとして、P ∪ {x} を母点とした際の x のボロネイ領域について、P を母点とした際の P の各点のボロネイ領域が占める割合で重みをつけて P 上の関数値を足し上げる方法がある。