ボロノイ図
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/20/Coloured_Voronoi_2D.svg/240px-Coloured_Voronoi_2D.svg.png)
定義
距離空間 (X, d) 内の有限な部分集合 P ⊂ X が与えられたとき、各点 p ∈ P を母点またはサイトと呼び、これに対して、X の中で「P の点の中で p が最も近い」点の集合
を p の(ボロノイ)領域と呼び、P の全ての点の領域を集めた集合(の誘導するセル複体)をボロノイ図と呼ぶ[1]。
ボロノイ領域の境界をボロノイ境界と呼び、各々のボロノイ境界の交点をボロノイ点と呼ぶ。
特徴
ボロノイ図およびボロノイ領域は以下の特徴を有する。
応用
- 最近点探索:与えられた点に最も近い母点を探す問題は直接的にのみならず、複雑な問題の一部分としても現れ、ボロノイ領域を応用したデータ構造を構築することで素早く探すことができる[2]。
- ロボット動作計画:障害物を避けて目的地に到達することが可能であれば、障害物を母点とするボロネイ境界上に経路をとることができる。このように空間をより低次元の骨格に置き換える手法はレトラクション・アプローチ(retraction approach)と呼ばれる[3]。
- ドロネー三角形分割:ユークリッド平面上のボロノイ図において、もしいずれの4母点も同一円上に無ければ[注 1]、ボロノイ領域が辺を共有する母点同士を線分で繋ぐことで母点全体の凸包をいくつかの三角形で分割したものが得られ、この三角形分割は理論・応用の両面において興味深い性質を持つ[5]。
- 補間:有限の点集合 P 上の値のみがわかっている関数のある点 x での値を推測する方法の一つとして、P ∪ {x} を母点とした際の x のボロネイ領域について、P を母点とした際の P の各点のボロネイ領域が占める割合で重みをつけて P 上の関数値を足し上げる方法がある[6]。
歴史
ボロノイ図の利用例は(きちんとそれが定式化される以前も含めれば)1644年のデカルトまで遡ることができる。ディリクレは1850年に二次形式についての自身の研究において、2次元と3次元のボロノイ図を用いている。このことから、ボロノイ図にはディリクレ空間分割(英: Dirichlet tessellation)の異称もある[2]。
ボロノイ図の名はロシア人数学者ゲオルギ・フェドセビッチ・ボロノイ (英語版)に因んだもので、彼は1908年に一般の n-次元の場合を定義、研究した。地球物理学や気象学で(降雨量測定のような)空間分布データの解析に用いられるボロノイ図は、アメリカ人気象学者アルフレッド・H・ティーセンenの名前を取って、ティーセン多角形(Thiessen polygonen)と呼ばれている。凝縮系物理学ではボロノイ細胞はウィグナー=サイツ単位セル(Wigner-Seitz unit cellen)として知られる。運動量の逆格子から得られるボロノイ図はブリルアンゾーン(Brillouin zoneen)と呼ばれる。リー群における一般格子に対し、そのボロノイ細胞のことを簡単に基本領域 (fundamental domainen) と呼ぶ。一般距離空間の場合には、そのボロノイ細胞のことをしばしば計量基本多項式(metric fundamental polygonen)と呼ぶ。
関連項目
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4a/Commons-logo.svg/30px-Commons-logo.svg.png)
脚注
注釈
出典
- ^ マトウシェク 2002, p. 115.
- ^ a b マトウシェク 2002, p. 116.
- ^ マトウシェク 2002, pp. 116, 117, 122.
- ^ マトウシェク 2002, p. 120.
- ^ マトウシェク 2002, pp. 117, 120–123.
- ^ マトウシェク 2002, p. 118.
文献
- 日本語
- J. マトウシェク 著、岡本 吉央 訳『離散幾何学講義』シュプリンガー・フェアラーク東京、2005年11月26日(原著2002年)。ISBN 4-431-71041-8。
- 外国語
外部リンク
- 『ボロノイ図とその3つの性質』 - 高校数学の美しい物語