Voronoi Diagramとは何？わかりやすく解説 Weblio辞書

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

ボロノイ図

読み方：ぼろのいず
【英】：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\,$ の選び方によってさまざまなボロノイ図が定義できる.

　中心が ${\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次元では平面の一部である.

　たとえば, 点を生成元とし, ユークリッド距離の逆数を距離とみなして定義されるボロノイ図は最遠点ボロノイ図 (farthest-point 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.