ボロノイ図
テンプレート:読み仮名は、ある距離空間上の任意の位置に配置された複数個の母点（テンプレート:Lang-en-short、サイト）に対して、同一距離空間上の他の点がどの母点に近いかによって領域分けされた図のことである。特に二次元ユークリッド平面の場合、領域の境界線は、各々の母点の二等分線の一部になる。母点の位置のみによって分割パターンが決定されるため、母点に規則性を持たせれば美しい図形を生み出すことが可能。
定義
距離空間 テンプレート:Math 内の有限な部分集合 テンプレート:Math が与えられたとき、各点 テンプレート:Math を母点またはサイトと呼び、これに対して、テンプレート:Mvar の中で「テンプレート:Mvar の点の中で テンプレート:Mvar が最も近い」点の集合
を テンプレート:Mvar の(ボロノイ)領域と呼び、テンプレート:Mvar の全ての点の領域を集めた集合（の誘導するセル複体）をボロノイ図と呼ぶテンプレート:Sfn。
ボロノイ領域の境界をボロノイ境界と呼び、各々のボロノイ境界の交点をボロノイ点と呼ぶ。
特徴
ボロノイ図およびボロノイ領域は以下の特徴を有する。
応用
- 最近点探索：与えられた点に最も近い母点を探す問題は直接的にのみならず、複雑な問題の一部分としても現れ、ボロノイ領域を応用したデータ構造を構築することで素早く探すことができるテンプレート:Sfn。
- ロボット動作計画：障害物を避けて目的地に到達することが可能であれば、障害物を母点とするボロノイ境界上に経路をとることができる。このように空間をより低次元の骨格に置き換える手法はレトラクション・アプローチ（retraction approach）と呼ばれるテンプレート:Sfn。
- ドロネー三角形分割：ユークリッド平面上のボロノイ図において、もしいずれの4母点も同一円上に無ければテンプレート:Efn2、ボロノイ領域が辺を共有する母点同士を線分で繋ぐことで母点全体の凸包をいくつかの三角形で分割したものが得られ、この三角形分割は理論・応用の両面において興味深い性質を持つテンプレート:Sfn。
- 補間：有限の点集合 テンプレート:Mvar 上の値のみがわかっている関数のある点 テンプレート:Mvar での値を推測する方法の一つとして、テンプレート:Math を母点とした際の テンプレート:Mvar のボロノイ領域について、テンプレート:Mvar を母点とした際の テンプレート:Mvar の各点のボロネイ領域が占める割合で重みをつけて テンプレート:Mvar 上の関数値を足し上げる方法があるテンプレート:Sfn。
歴史
ボロノイ図の利用例は（きちんとそれが定式化される以前も含めれば）1644年のデカルトまで遡ることができる。ディリクレは1850年に二次形式についての自身の研究において、2次元と3次元のボロノイ図を用いている。このことから、ボロノイ図にはディリクレ空間分割（テンプレート:Lang-en-short）の異称もあるテンプレート:Sfn。
ボロノイ図の名はロシア人数学者テンプレート:仮リンクに因んだもので、彼は1908年に一般の n-次元の場合を定義、研究した。地球物理学や気象学で（降雨量測定のような）空間分布データの解析に用いられるボロノイ図は、アメリカ人気象学者アルフレッド・H・ティーセンテンプレート:Supの名前を取って、ティーセン多角形（テンプレート:Lang）と呼ばれている。凝縮系物理学ではボロノイ細胞はウィグナー=サイツ単位セル（テンプレート:Lang）として知られる。運動量の逆格子から得られるボロノイ図はブリルアンゾーン（テンプレート:Lang）と呼ばれる。リー群における一般格子に対し、そのボロノイ細胞のことを簡単に基本領域 テンプレート:Lang と呼ぶ。一般距離空間の場合には、そのボロノイ細胞のことをしばしば計量基本多項式（テンプレート:Lang）と呼ぶ。
関連項目
脚注
注釈
出典
文献
- 日本語
- 外国語