ボロノイ図

240px|thumb|ボロノイ図の一例個々の色分けが一つの領域を表すは、ある距離空間上の任意の位置に配置された複数個の母点（、サイト）に対して、同一距離空間上の他の点がどの母点に近いかによって領域分けされた図のことである。特に二次元ユークリッド平面の場合、領域の境界線は、各々の母点の二等分線の一部になる。母点の位置のみによって分割パターンが決定されるため、母点に規則性を持たせれば美しい図形を生み出すことが可能。

定義距離空間内の有限な部分集合が与えられたとき、各点を母点またはサイトと呼び、これに対して、の中で「の点の中でが最も近い」点の集合

をの(ボロノイ)領域と呼び、の全ての点の領域を集めた集合（の誘導するセル複体）をボロノイ図と呼ぶ。

ボロノイ領域の境界をボロノイ境界と呼び、各々のボロノイ境界の交点をボロノイ点と呼ぶ。

特徴ボロノイ図およびボロノイ領域は以下の特徴を有する。ボロノイ領域は凸領域である。ボロノイ点は、各々のボロノイ境界の母点から等距離の位置に存在している。特に二次元ユークリッド平面の場合、母点を中心とした円の交点となる。

応用最近点探索：与えられた点に最も近い母点を探す問題は直接的にのみならず、複雑な問題の一部分としても現れ、ボロノイ領域を応用したデータ構造を構築することで素早く探すことができる。

ロボット動作計画：障害物を避けて目的地に到達することが可能であれば、障害物を母点とするボロノイ境界上に経路をとることができる。このように空間をより低次元の骨格に置き換える手法はレトラクション・アプローチ（retraction approach）と呼ばれる。ドロネー三角形分割：ユークリッド平面上のボロノイ図において、もしいずれの4母点も同一円上に無ければ、ボロノイ領域が辺を共有する母点同士を線分で繋ぐことで母点全体の凸包をいくつかの三角形で分割したものが得られ、この三角形分割は理論・応用の両面において興味深い性質を持つ。補間：有限の点集合上の値のみがわかっている関数のある点での値を推測する方法の一つとして、を母点とした際ののボロノイ領域について、を母点とした際のの各点のボロネイ領域が占める割合で重みをつけて上の関数値を足し上げる方法がある。

歴史ボロノイ図の利用例は（きちんとそれが定式化される以前も含めれば）1644年のデカルトまで遡ることができる。ディリクレは1850年に二次形式についての自身の研究において、2次元と3次元のボロノイ図を用いている。このことから、ボロノイ図にはディリクレ空間分割（）の異称もある。

ボロノイ図の名はロシア人数学者に因んだもので、彼は1908年に一般の n-次元の場合を定義、研究した。地球物理学や気象学で（降雨量測定のような）空間分布データの解析に用いられるボロノイ図は、アメリカ人気象学者アルフレッド・H・ティーセンの名前を取って、ティーセン多角形（）と呼ばれている。凝縮系物理学ではボロノイ細胞はウィグナー=サイツ単位セル（）として知られる。運動量の逆格子から得られるボロノイ図はブリルアンゾーン（）と呼ばれる。リー群における一般格子に対し、そのボロノイ細胞のことを簡単に基本領域と呼ぶ。一般距離空間の場合には、そのボロノイ細胞のことをしばしば計量基本多項式（）と呼ぶ。

ボロノイ図

Źródło i licencja