ボロノイ図とは - OR事典 Weblio辞書

Weblio 辞書 > 学問 > OR事典 > ボロノイ図の意味・解説

OR事典

ボロノイ図

概要

空間に, 互いに共通部分をもたない有限個の図形を配置すると, それぞれの図形のまわりには他の図形より自分に近い点からなる領域が定まる. この領域をその図形のボロノイ領域という. 空間のボロノイ領域への分割をボロノイ図といい, はじめに配置された図形をこのボロノイ図の生成元という. 生成元, 距離, 空間の次元の選び方によってボロノイ図には多くの種類がある. ボロノイ図は, 勢力圏を表すものと解釈でき, 地理的最適化などに応用されている.

詳説

空間に生成元とよばれるいくつかの図形が配置されているとき, 空間の各点を最も近い生成元へ割り当てた構造をボロノイ図 (Voronoi diagram) という. 一つの生成元に割り当てられた点全体がなす領域を, その生成元のボロノイ領域または勢力圏という.

空間 $E\,$ に配置された生成元を $g_1, g_2, \cdots , g_n\,$ とし, 生成元の集合を $G\,$ とする. 任意の点 ${\rm P}\in E\,$ から $g_i\,$ までの距離を $d({\rm P}, g_i)\,$ で表す. $g_i\,$ のボロノイ領域 $R(G; g_i)\,$ は

$R(G; g_i) = \{ {\rm P} \in E \mid d({\rm P}, g_i) < d({\rm P}, g_j), j \ne i\}\,$

と表すことができる. $E\,$ は, $R(G; g_1), R(G; g_2), \cdots ,R(G; g_n)\,$ とそれらの境界に分割されるが, その分割構造がボロノイ図である. 空間 $E\,$ と, 生成元 $g_i \; (i=1, 2, \cdots , n)\,$ と距離 $d\,$ の選び方によってさまざまなボロノイ図が定義できる.

点を生成元とし, ユークリッド距離を距離とするボロノイ図は点ボロノイ図 (Voronoi diagram for points) とよばれる. 2次元では, ボロノイ領域の境界は, 両側の生成元を結ぶ線分の垂直二等分線の上にあり, 3つのボロノイ領域の境界が共有する点はまわりの 3 個の生成元を通る円の中心である.

点ボロノイ図に対して, ボロノイ領域が隣り合う生成元を線分で結ぶことによってできる図形はドロネー図 (Delaunay diagram) とよばれる.

互いに交差しない線分を生成元とし, ユークリッド距離を距離とするボロノイ図は線分ボロノイ図 (Voronoi diagram for line segments) よばれる. 2 次元線分ボロノイ図の境界は線分と放物線の一部によって構成される.

中心が ${\rm P}_i\,$ , 半径が $r_i\,$ の円を $c_i\,$ とする. 点 ${\rm P}\,$ に対して $|{\rm P}-{\rm P}_i|^2-{r_i}^2\,$ を, 点 ${\rm P}\,$ と円 $c_i\,$ のラゲール (Laguerre) 距離という. ただし $|{\rm P}-{\rm Q}|\,$ は 2 点 ${\rm P}, {\rm Q}\,$ のユークリッド距離を表す. 円 $c_1, c_2, \cdots , c_n\,$ を生成元とし, ラゲール距離を距離とするボロノイ図をラゲールボロノイ図 (Laguere Voronoi diagram) またはパワー図 (power diagram) とよぶ. ラゲールボロノイ図の境界は超平面の一部である. 特に2次元では直線の一部であり, 3次元では平面の一部である.

このほかにも $\mbox{L}_p\,$ -距離, ハウスドルフ距離などさまざまな距離を用いてボロノイ図が定義できる. このように一般の距離に基づいて定義されるボロノイ図を一般距離ボロノイ図 (Voronoi diagram based on a general distance) とよぶ.

たとえば, 点を生成元とし, ユークリッド距離の逆数を距離とみなして定義されるボロノイ図は最遠点ボロノイ図 (farthest-point Voronoi diagram) とよばれる. このボロノイ図では, 他の生成元より自分の方が離れているという領域がそれぞれの生成元のボロノイ領域となる. 空でないボロノイ領域をもつのは, 生成元の凸包の境界上に現れる生成元のみである.

生成元がその位置や形を時間とともに変えると, 対応するボロノイ図も時間とともに変化する. このように時間の関数となるボロノイ図は動的ボロノイ図 (dynamic Voronoi diagram) とよばれる. 動的ボロノイ図は, 飛行機やロボットが互いに接近し過ぎないよう監視するときなどに役立つ.

平面上に与えられた有限個の点の集合を $S\,$ とする. $S\,$ を含む最小の円を $S\,$ の最小包含円 (minimum enclosing circle) という. $S\,$ の最小包含円は, $S\,$ のちょうど 2 個の点を境界上にもつか, 3個以上の点を境界上にもつかのいずれかである. 前者の場合の最小包含円の中心は $S\,$ を生成元集合とする最遠点ボロノイ図の辺上にあり, 後者の場合の最小包含円の中心はその最遠点ボロノイ図の頂点のいずれかと一致する.

平面上の一つの多角形を $T\,$ とし, $T\,$ 内に指定された有限個の点の集合を $S\,$ とする. $T\,$ 内に中心をもち, $S\,$ の要素を一つも内部に含まない円を空円といい, その中で半径が最大のものを最大空円 (maximum empty circle) という. 最大空円の中心は, $T\,$ の頂点か, $S\,$ を生成元集合とするボロノイ図の頂点か, あるいはボロノイ図の辺と $T\,$ の境界辺の交点のいずれかである.

ボロノイ図の効率のよい構成法はたくさん知られている. たとえば 2次元では, 点ボロノイ図, 線分ボロノイ図, ラゲールボロノイ図が ${\rm O}(n\log n)\,$ の計算量で構成できる. $d\,$ 次元空間 ( $d \geq 3\,$ ) における点ボロノイ図とラゲールボロノイ図は, ${\rm O}(n^{\lfloor (d+1)/2\rfloor})\,$ の計算量で構成できる. ただし $\lfloor x \rfloor\,$ は $x\,$ 以下の最大の整数である.

ボロノイ図に関する詳しい解説には [1, 2, 3] がある.

参考文献

[1] F. Aurenhammer, "Voronoi Diagrams -A Survey of a Fundamental Geometric Data Structure," ACM Computing Surveys, 23 (1991), 345-405.

[2] A. Okabe, B. Boots, K. Sugihara and S.-N. Chiu, Spatial Tessellations -Concepts and Applications of Voronoi Diagrams, 2nd Edition, John Wiley and Sons, Inc., Chichester, 2000.

[3] S. Fortune, "Voronoi Diagrams and Delaunay Triangulations," in Computing in Euclidean Geometry, 2nd Edition, D. -Z. Du and F. Hwang, eds., World Scientific, Singapore, 225-265, 1995.

「OR事典」の他の用語

計算幾何：

ドロネー図ハフ変換バケット法ボロノイ図ポリマトロイドマッチングラゲールボロノイ図

索引トップ用語の索引ランキングカテゴリー

ウィキペディア

ボロノイ図

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2011/10/21 09:32 UTC 版)

ボロノイ図の一例個々の色分けが一つの領域を表す

ボロノイ図（ボロノイず、英語: Voronoi diagram）は、ある距離空間上の任意の位置に配置された複数個の点（母点）に対して、同一距離空間上の他の点がどの母点に近いかによって領域分けされた図のことである。特に二次元ユークリッド平面の場合、領域の境界線は、各々の母点の二等分線の一部になる。

[続きの解説]

「ボロノイ図」の続きの解説一覧

1 ボロノイ図とは
2 ボロノイ図の概要

索引トップ用語の索引ランキングカテゴリー

ボロノイ図に関係した商品

【送料無料】なわばりの数理モデル ボロノイ図からの数理工学入門 / 杉原厚吉【単行本】HMV ローソンホットステーション R
【送料無料】コンピュータ・ジオメトリ計算幾何学: アルゴリズムと応用第3版 / マーク・ド・バーグ【単行本】HMV ローソンホットステーション R
【送料無料】コンピュ-タ・ジオメトリ第3版楽天ブックス

>> 「ボロノイ図」を含む用語の索引

ボロノイ図のページへのリンク

ボロノイ図のページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。

1		TPP
2		ガナッシュ
3		再臨界
4		今井遥
5		面目を失う
6		更迭
7		あざとい
8		四大陸
9		先負
10		粉糖

11		リツイート
12		.m4a
13		うしのしっぺ
14		ベキサロテン
15		牧嶋博子
16		及第点
17		コシノミチコ
18		アウターライズ地震
19		こざとへん
20		ホキ

21		捗る
22		藤本有紀
23		コシノヒロコ
24		共益費
25		未満
26		ほたえる
27		高階通憲
28		プラリネ
29		ご指導ご鞭撻
30		遡及


	Copyright (C) 2012 （社）日本オペレーションズ・リサーチ学会 All rights reserved.
	All text is available under the terms of the GNU Free Documentation License. この記事は、ウィキペディアのボロノイ図 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

ボロノイ図とは？

OR事典

ボロノイ図

概要

詳説

ウィキペディア

ボロノイ図