ボロノイ図
ボロノイ図（ボロノイず、英語: Voronoi diagram）は、ある距離空間上の任意の位置に配置された複数個の点（母点）に対して、同一距離空間上の他の点がどの母点に近いかによって領域分けされた図のことである。特に二次元ユークリッド平面の場合、領域の境界線は、各々の母点の二等分線の一部になる。母点の位置のみによって分割パターンが決定されるため、母点に規則性を持たせれば美しい図形を生み出すことが可能。
定義
距離空間内の有限部分集合 P = {p1, p2, ..., pn} および、距離関数 d に対して
- [math] V(p_i) = \{p\ |\ d(p, p_i) \le d(p, p_j),\ j\ne i\}[/math]
で構成される領域 V(pi) を pi のボロノイ領域と呼ぶ。また、{V(p1), V(p2), ..., V(pn)} をボロノイ図と呼ぶ。
ボロノイ領域の境界をボロノイ境界と呼び、各々のボロノイ境界の交点をボロノイ点と呼ぶ。
歴史
ボロノイ図の利用例は（きちんとそれが定式化される以前も含めれば）1644年のデカルトまで遡ることができる。ディリクレは1850年に二次形式についての自身の研究において、2次元と3次元のボロノイ図を用いている。
ボロノイ図の名はロシア人数学者ゲオルギ・フェドセビッチ・ボロノイenにちなんだもので、彼は1908年に一般の n-次元の場合を定義、研究した。地球物理学や気象学で（降雨量測定のような）空間分布データの解析に用いられるボロノイ図は、アメリカ人気象学者アルフレッド・H・ティーセンenの名前を取って、ティーセン多角形（Thiessen polygonen）と呼ばれている。凝縮系物理学ではボロノイ細胞はウィグナー=サイツ単位セル（Wigner-Seitz unit cellen）として知られる。運動量の逆格子から得られるボロノイ図はブリルアンゾーン（Brillouin zoneen）と呼ばれる。リー群における一般格子に対し、そのボロノイ細胞のことを簡単に基本領域 (fundamental domainen) と呼ぶ。一般距離空間の場合には、そのボロノイ細胞のことをしばしば計量基本多項式（metric fundamental polygonen）と呼ぶ。
特徴
ボロノイ図およびボロノイ領域は以下の特徴を有する。
- ボロノイ領域は凸領域である。
- ボロノイ点は、各々のボロノイ境界の母点から等距離の位置に存在している。特に二次元ユークリッド平面の場合、母点を中心とした円の交点となる。