ボロノイ図のソースを表示

{{出典の明記|date=2011-10}}
[[画像:coloured Voronoi 2D.svg|240px|thumb|ボロノイ図の一例 個々の色分けが一つの領域を表す]]
{{読み仮名|'''ボロノイ図'''|ボロノイず、{{lang-en-short|Voronoi diagram}}}}は、ある[[距離空間]]上の任意の位置に配置された複数個の[[点 (数学)|母点]]（{{lang-en-short|site|links=no}}、サイト）に対して、同一距離空間上の他の点がどの母点に近いかによって[[領域 (解析学)|領域]]分けされた図のことである。特に二次元[[ユークリッド空間|ユークリッド平面]]の場合、領域の境界線は、各々の母点の[[二等分線]]の一部になる。母点の位置のみによって分割パターンが決定されるため、母点に規則性を持たせれば美しい図形を生み出すことが可能。

== 定義 ==
距離空間 {{math|(''X'', ''d'')}} 内の[[有限集合|有限]]な[[部分集合]] {{math|''P'' &subset; ''X''}} が与えられたとき、各点 {{math|''p'' &isin; ''P''}} を'''母点'''または'''サイト'''と呼び、これに対して、{{mvar|X}} の中で「{{mvar|P}} の点の中で {{mvar|p}} が最も近い」点の集合
: <math>V(p) = \{x \in X \mid \forall q \in P \; [d(x, p) \le d(x, q)]\}</math>
を {{mvar|p}} の'''(ボロノイ)領域'''と呼び、{{mvar|P}} の全ての点の領域を集めた集合（の誘導するセル複体）を'''ボロノイ図'''と呼ぶ{{Sfn|マトウシェク|2002|p=115}}。

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

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

== 応用 ==
* [[最近傍探索|最近点探索]]：与えられた点に最も近い母点を探す問題は直接的にのみならず、複雑な問題の一部分としても現れ、ボロノイ領域を応用したデータ構造を構築することで素早く探すことができる{{Sfn|マトウシェク|2002|p=116}}。
<!-- ** [[校区]]の設定
** [[画像]]データの[[データ圧縮|圧縮]]
** 離散データの集約 -->
* [[ロボット]]動作計画：障害物を避けて目的地に到達することが可能であれば、障害物を母点とするボロノイ境界上に経路をとることができる。このように空間をより低次元の骨格に置き換える手法はレトラクション・アプローチ（retraction approach）と呼ばれる{{Sfn|マトウシェク|2002|pp=116,117,122}}。
* [[ドロネー三角形分割]]：ユークリッド平面上のボロノイ図において、もしいずれの4母点も同一円上に無ければ{{Efn2|仮定が満たされない場合は三角形分割になるとは限らない。この場合はドロネー空間分割（Delaunay tessellation）と呼ばれる{{Sfn|マトウシェク|2002|p=120}}。}}、ボロノイ領域が辺を共有する母点同士を[[線分]]で繋ぐことで母点全体の[[凸包]]をいくつかの三角形で分割したものが得られ、この三角形分割は理論・応用の両面において興味深い性質を持つ{{Sfn|マトウシェク|2002|pp=117,120&ndash;123}}。
* [[補間]]：有限の点集合 {{mvar|P}} 上の値のみがわかっている関数のある点 {{mvar|x}} での値を推測する方法の一つとして、{{math|''P'' &cup; {{(}}''x''{{)}}}} を母点とした際の {{mvar|x}} のボロノイ領域について、{{mvar|P}} を母点とした際の {{mvar|P}} の各点のボロネイ領域が占める割合で重みをつけて {{mvar|P}} 上の関数値を足し上げる方法がある{{Sfn|マトウシェク|2002|p=118}}。

== 歴史 ==
ボロノイ図の利用例は（きちんとそれが定式化される以前も含めれば）1644年の[[ルネ・デカルト|デカルト]]まで遡ることができる。[[ディリクレ]]は1850年に[[二次形式]]についての自身の研究において、2次元と3次元のボロノイ図を用いている。このことから、ボロノイ図にはディリクレ空間分割（{{lang-en-short|Dirichlet tessellation|links=no}}）の異称もある{{Sfn|マトウシェク|2002|p=116}}。

ボロノイ図の名はロシア人数学者{{仮リンク|ゲオルギ・フェドセビッチ・ボロノイ |en|Georgy Voronoy }}に因んだもので、彼は1908年に一般の ''n''-次元の場合を定義、研究した。[[地球物理学]]や[[気象学]]で（降雨量測定のような）空間分布データの解析に用いられるボロノイ図は、アメリカ人気象学者アルフレッド・H・ティーセン{{sup|[[:en:Alfred H. Thiessen|en]]}}の名前を取って、'''ティーセン多角形'''（{{lang|en|Thiessen polygon{{sup|[[:en:Thiessen polygon|en]]}}}}）と呼ばれている。[[物性物理学|凝縮系物理学]]ではボロノイ細胞は[[ウィグナーザイツ胞|ウィグナー=サイツ単位セル]]（{{lang|en|Wigner-Seitz unit cell{{sup|[[:en:Wigner-Seitz unit cell|en]]}}}}）として知られる。運動量の逆格子から得られるボロノイ図は[[ブリルアンゾーン]]（{{lang|en|Brillouin zone{{sup|[[:en:Brillouin zone|en]]}}}}）と呼ばれる。[[リー群]]における一般格子に対し、そのボロノイ細胞のことを簡単に[[基本領域]] {{lang|en|(fundamental domain{{sup|[[:en:fundamental domain|en]]}})}} と呼ぶ。一般距離空間の場合には、そのボロノイ細胞のことをしばしば[[計量基本多項式]]（{{lang|en|metric fundamental polygon{{sup|[[:en:metric fundamental polygon|en]]}}}}）と呼ぶ。

== 関連項目 ==
{{commonscat|Voronoi diagrams}}
* [[ドロネー図]]
* [[離散ボロノイ図]]
* [[最近傍探索]]

== 脚注 ==
{{脚注ヘルプ}}
=== 注釈 ===
{{notelist2}}<!-- {{Efn2| }} で注釈追加  -->
=== 出典 ===
{{Reflist|colwidth=25em}}<!-- {{Sfn| }} で出典追加 -->
=== 文献 ===
; 日本語
* {{Cite book|和書|author=J. マトウシェク|translator=岡本 吉央|title=離散幾何学講義|date=2005-11-26|publisher=[[シュプリンガー・フェアラーク東京]]|isbn=4-431-71041-8|ref={{SfnRef|マトウシェク|2002}}|authorlink=:en:Jiří_Matoušek_(mathematician)|origyear=2002}}
; 外国語

== 外部リンク ==
* {{高校数学の美しい物語|1194|ボロノイ図とその３つの性質}}

{{Normdaten}}
{{DEFAULTSORT:ほろのいす}}
[[Category:計算幾何学]]
[[Category:離散幾何学]]
[[Category:ダイアグラム]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]