ボロノイ図とは？わかりやすく解説

辞書 類語・対義語辞典 英和・和英辞典 日中中日辞典 日韓韓日辞典 古語辞典

その他の辞書▼
- 手話辞典
- インドネシア語辞典
- タイ語辞典
- ベトナム語辞典

Weblio 辞書ヘルプ

556の専門辞書や国語辞典百科事典から一度に検索!

無料の翻訳ならWeblio翻訳！

初めての方へ参加元一覧

Weblio 辞書 > 辞書・百科事典 > デジタル大辞泉 > ボロノイ図の意味・解説

デジタル大辞泉

索引トップランキング凡例

ボロノイ‐ず〔‐ヅ〕【ボロノイ図】

読み方：ぼろのいず

複数の点が散在する面や空間を、近接する点どうしを結ぶ線分の垂直二等分線（空間の場合は垂直二等分面）で分割してできる図や構造。二次元の場合、複数の多角形（ボロノイ領域）で埋め尽くされる。三次元の場合、複数の多面体（ボロノイ多面体）で埋め尽くされ、石鹸の泡のような構造となる。それぞれの境界をボロノイ境界、このような分割をボロノイ分割と呼ぶ。ロシアの数学者ゲオルギー‐ボロノイにちなむ。

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

ボロノイ図

読み方：ぼろのいず
【英】：Voronoi diagram

概要

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

詳説

　空間に生成元とよばれるいくつかの図形が配置されているとき, 空間の各点を最も近い生成元へ割り当てた構造をボロノイ図 (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）』 (2021/07/08 08:05 UTC 版)

ボロノイ図（ボロノイず、英: Voronoi diagram）は、ある距離空間上の任意の位置に配置された複数個の点（母点）に対して、同一距離空間上の他の点がどの母点に近いかによって領域分けされた図のことである。特に二次元ユークリッド平面の場合、領域の境界線は、各々の母点の二等分線の一部になる。母点の位置のみによって分割パターンが決定されるため、母点に規則性を持たせれば美しい図形を生み出すことが可能。

[続きの解説]

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

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

>> 「ボロノイ図」を含む用語の索引
ボロノイ図のページへのリンク

辞書ショートカット

1 デジタル大辞泉
2 OR事典
3 ウィキペディア

カテゴリ一覧

＋ビジネス

＋業界用語

＋コンピュータ

＋自動車・バイク

＋船

＋建築・不動産

＋ヘルスケア

＋スポーツ

＋辞書・百科事典

すべての辞書の索引

Weblioのサービス

「ボロノイ図」の関連用語

1

ボロノイ分割 デジタル大辞泉

100% |||||

2

ボロノイ境界 デジタル大辞泉

100% |||||

3

ボロノイ多面体 デジタル大辞泉

100% |||||

4

ボロノイ領域 デジタル大辞泉

100% |||||

5

点ボロノイ図

100% |||||

6

離散ボロノイ図

百科事典

100% |||||

7

動的ボロノイ図

100% |||||

8

線分ボロノイ図

100% |||||

9

一般距離ボロノイ図

96% |||||

10

最小包含円

78% |||||

ボロノイ図のお隣キーワード

ボロニーズ

ボロネッドゥ

ボロネツ修道院

ボロネーゼ

ボロノイ分割

ボロノイ図

ボロノイ境界

ボロノイ多面体

ボロノイ領域

ボロビツカヤ塔

ボロフェスタ

ボロフェン

検索ランキング

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


	(C)Shogakukan Inc. 株式会社小学館
	Copyright (C) 2024 （社）日本オペレーションズ・リサーチ学会 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の元に提供されております。

ビジネス｜業界用語｜コンピュータ｜電車｜自動車・バイク｜船｜工学｜建築・不動産｜学問
 文化｜生活｜ヘルスケア｜趣味｜スポーツ｜生物｜食品｜人名｜方言｜辞書・百科事典

ご利用にあたって

・Weblio辞書とは

・検索の仕方

・利用規約

・プライバシーポリシー

・サイトマップ

便利な機能

・ウェブリオのアプリ

・画像から探す

お問合せ・ご要望

・お問い合わせ

会社概要

・公式企業ページ

・会社情報

・採用情報

ウェブリオのサービス

・Weblio 辞書

・類語・対義語辞典

・英和辞典・和英辞典

・Weblio翻訳

・日中中日辞典

・日韓韓日辞典

・フランス語辞典

・インドネシア語辞典

・タイ語辞典

・ベトナム語辞典

・古語辞典

・手話辞典

・IT用語辞典バイナリ

・おすすめのプログラミングスクール情報「Livifun」

©2024 GRAS Group, Inc.RSS