https://orsj-ml.org/orwiki/wiki/index.php?action=history&feed=atom&title=%E3%83%9C%E3%83%AD%E3%83%8E%E3%82%A4%E5%9B%B3
ボロノイ図 - 版の履歴
2026-04-16T23:41:45Z
このウィキのこのページに関する変更履歴
MediaWiki 1.35.3
https://orsj-ml.org/orwiki/wiki/index.php?title=%E3%83%9C%E3%83%AD%E3%83%8E%E3%82%A4%E5%9B%B3&diff=9699&oldid=prev
Imahori: 基礎編と用語編のマージ
2008-03-13T14:22:52Z
<p>基礎編と用語編のマージ</p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="ja">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← 古い版</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">2008年3月13日 (木) 14:22時点における版</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >1行目:</td>
<td colspan="2" class="diff-lineno">1行目:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>'''【ぼろのいず (Voronoi diagram)】'''</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>'''【ぼろのいず (Voronoi diagram)】'''</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">=== 概要 ===</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>空間に, 互いに共通部分をもたない有限個の図形を配置すると, それぞれの図形のまわりには他の図形より自分に近い点からなる領域が定まる. この領域をその図形のボロノイ領域という. 空間のボロノイ領域への分割をボロノイ図といい, はじめに配置された図形をこのボロノイ図の生成元という. 生成元, 距離, 空間の次元の選び方によってボロノイ図には多くの種類がある. ボロノイ図は, 勢力圏を表すものと解釈でき, 地理的最適化などに応用されている.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>空間に, 互いに共通部分をもたない有限個の図形を配置すると, それぞれの図形のまわりには他の図形より自分に近い点からなる領域が定まる. この領域をその図形のボロノイ領域という. 空間のボロノイ領域への分割をボロノイ図といい, はじめに配置された図形をこのボロノイ図の生成元という. 生成元, 距離, 空間の次元の選び方によってボロノイ図には多くの種類がある. ボロノイ図は, 勢力圏を表すものと解釈でき, 地理的最適化などに応用されている.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">詳しくは</del>[[<del class="diffchange diffchange-inline">《ボロノイ図》</del>|<del class="diffchange diffchange-inline">基礎編：ボロノイ図</del>]]<del class="diffchange diffchange-inline">を参照</del>.</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">=== 詳説 ===</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> 空間に生成元とよばれるいくつかの図形が配置されているとき, 空間の各点を最も近い生成元へ割り当てた構造を</ins>[[<ins class="diffchange diffchange-inline">ボロノイ図]] (Voronoi diagram) という. 一つの生成元に割り当てられた点全体がなす領域を, その生成元のボロノイ領域または勢力圏という. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> 空間 <math>E\, </math> に配置された生成元を <math>g_1, g_2, \cdots , g_n\, </math> とし, 生成元の集合を <math>G\, </math>とする. 任意の点 <math>{\rm P}\in E\, </math> から <math>g_i\, </math> までの距離を <math>d({\rm P}, g_i)\, </math> で表す. <math>g_i\, </math> のボロノイ領域 <math>R(G; g_i)\, </math> は</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"><center></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"><math>R(G; g_i) = \{ {\rm P} \in E \mid d({\rm P}, g_i) < d({\rm P}, g_j), j \ne i\}\, </math></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"></center></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">と表すことができる. <math>E\, </math> は, <math>R(G; g_1), R(G; g_2), \cdots ,R(G; g_n)\, </math> とそれらの境界に分割されるが, その分割構造がボロノイ図である. 空間 <math>E\, </math> と, 生成元 <math>g_i \; (i=1, 2, \cdots , n)\, </math> と距離 <math>d\, </math> の選び方によってさまざまなボロノイ図が定義できる. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> 点を生成元とし, ユークリッド距離を距離とするボロノイ図は[[点ボロノイ図]] (Voronoi diagram for points) とよばれる. 2次元では, ボロノイ領域の境界は, 両側の生成元を結ぶ線分の垂直二等分線の上にあり, 3つのボロノイ領域の境界が共有する点はまわりの 3 個の生成元を通る円の中心である. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> 点ボロノイ図に対して, ボロノイ領域が隣り合う生成元を線分で結ぶことによってできる図形は[[ドロネー図]] (Delaunay diagram) とよばれる. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> 互いに交差しない線分を生成元とし, ユークリッド距離を距離とするボロノイ図は[[線分ボロノイ図]] (Voronoi diagram for line segments) よばれる. 2 次元線分ボロノイ図の境界は線分と放物線の一部によって構成される. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> 中心が <math>{\rm P}_i\, </math>, 半径が <math>r_i\, </math> の円を <math>c_i\, </math> とする. 点<math>{\rm P}\, </math> に対して<math>|{\rm P}-{\rm P}_i</ins>|<ins class="diffchange diffchange-inline">^2-{r_i}^2\, </math>を, 点 <math>{\rm P}\, </math> と円 <math>c_i\, </math> のラゲール (Laguerre) 距離という. ただし<math>|{\rm P}-{\rm Q}|\, </math> は 2 点 <math>{\rm P}, {\rm Q}\, </math> のユークリッド距離を表す. 円 <math>c_1, c_2, \cdots , c_n\, </math> を生成元とし, ラゲール距離を距離とするボロノイ図を[[ラゲールボロノイ図]] (Laguere Voronoi diagram) またはパワー図 (power diagram) とよぶ. ラゲールボロノイ図の境界は超平面の一部である. 特に2次元では直線の一部であり, 3次元では平面の一部である. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> このほかにも <math>\mbox{L}_p\, </math>-距離, ハウスドルフ距離などさまざまな距離を用いてボロノイ図が定義できる. このように一般の距離に基づいて定義されるボロノイ図を[[一般距離ボロノイ図]] (Voronoi diagram based on a general distance) とよぶ. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> たとえば, 点を生成元とし, ユークリッド距離の逆数を距離とみなして定義されるボロノイ図は最遠点ボロノイ図 (farthest-point Voronoi diagram) とよばれる. このボロノイ図では, 他の生成元より自分の方が離れているという領域がそれぞれの生成元のボロノイ領域となる. 空でないボロノイ領域をもつのは, 生成元の凸包の境界上に現れる生成元のみである. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> 生成元がその位置や形を時間とともに変えると, 対応するボロノイ図も時間とともに変化する. このように時間の関数となるボロノイ図は[[動的ボロノイ図]] (dynamic Voronoi diagram) とよばれる. 動的ボロノイ図は, 飛行機やロボットが互いに接近し過ぎないよう監視するときなどに役立つ. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> 平面上に与えられた有限個の点の集合を <math>S\, </math> とする. <math>S\, </math> を含む最小の円を<math>S\, </math> の[[最小包含円]] (minimum enclosing circle) という. <math>S\, </math> の最小包含円は, <math>S\, </math> のちょうど 2 個の点を境界上にもつか, 3個以上の点を境界上にもつかのいずれかである. 前者の場合の最小包含円の中心は<math>S\, </math> を生成元集合とする最遠点ボロノイ図の辺上にあり, 後者の場合の最小包含円の中心はその最遠点ボロノイ図の頂点のいずれかと一致する. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> 平面上の一つの多角形を <math>T\, </math> とし, <math>T\, </math> 内に指定された有限個の点の集合を <math>S\, </math> とする. <math>T\, </math> 内に中心をもち, <math>S\, </math> の要素を一つも内部に含まない円を空円といい, その中で半径が最大のものを[[最大空円]] (maximum empty circle) という. 最大空円の中心は, <math>T\, </math> の頂点か, <math>S\, </math> を生成元集合とするボロノイ図の頂点か, あるいはボロノイ図の辺と <math>T\, </math> の境界辺の交点のいずれかである. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> ボロノイ図の効率のよい構成法はたくさん知られている. たとえば 2次元では, 点ボロノイ図, 線分ボロノイ図, ラゲールボロノイ図が<math>{\rm O}(n\log n)\, </math> の計算量で構成できる. <math>d\, </math> 次元空間 (<math>d \geq 3\, </math>) における点ボロノイ図とラゲールボロノイ図は, <math>{\rm O}(n^{\lfloor (d+1)/2\rfloor})\, </math> の計算量で構成できる. ただし <math>\lfloor x \rfloor\, </math> は <math>x\, </math> 以下の最大の整数である. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> ボロノイ図に関する詳しい解説には [1, 2, 3</ins>] <ins class="diffchange diffchange-inline">がある. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">----</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">'''参考文献'''</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">[1</ins>] <ins class="diffchange diffchange-inline">F. Aurenhammer, "Voronoi Diagrams -A Survey of a Fundamental Geometric Data Structure," ''ACM Computing Surveys'', '''23''' (1991), 345-405</ins>. <ins class="diffchange diffchange-inline"> </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">[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. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">[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.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">[[Category:計算幾何|ぼろのいず]]</ins></div></td></tr>
</table>
Imahori
https://orsj-ml.org/orwiki/wiki/index.php?title=%E3%83%9C%E3%83%AD%E3%83%8E%E3%82%A4%E5%9B%B3&diff=8346&oldid=prev
2007年8月8日 (水) 12:07にKanda.kによる
2007-08-08T12:07:53Z
<p></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="ja">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← 古い版</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">2007年8月8日 (水) 12:07時点における版</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l2" >2行目:</td>
<td colspan="2" class="diff-lineno">2行目:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>空間に, 互いに共通部分をもたない有限個の図形を配置すると, それぞれの図形のまわりには他の図形より自分に近い点からなる領域が定まる. この領域をその図形のボロノイ領域という. 空間のボロノイ領域への分割をボロノイ図といい, はじめに配置された図形をこのボロノイ図の生成元という. 生成元, 距離, 空間の次元の選び方によってボロノイ図には多くの種類がある. ボロノイ図は, 勢力圏を表すものと解釈でき, 地理的最適化などに応用されている.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>空間に, 互いに共通部分をもたない有限個の図形を配置すると, それぞれの図形のまわりには他の図形より自分に近い点からなる領域が定まる. この領域をその図形のボロノイ領域という. 空間のボロノイ領域への分割をボロノイ図といい, はじめに配置された図形をこのボロノイ図の生成元という. 生成元, 距離, 空間の次元の選び方によってボロノイ図には多くの種類がある. ボロノイ図は, 勢力圏を表すものと解釈でき, 地理的最適化などに応用されている.</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">詳しくは[[《ボロノイ図》|基礎編：ボロノイ図]]を参照.</ins></div></td></tr>
</table>
Kanda.k
https://orsj-ml.org/orwiki/wiki/index.php?title=%E3%83%9C%E3%83%AD%E3%83%8E%E3%82%A4%E5%9B%B3&diff=7125&oldid=prev
Orsjwiki: "ボロノイ図" を保護しました。 [edit=sysop:move=sysop]
2007-07-20T02:09:37Z
<p>"ボロノイ図" を保護しました。 [edit=sysop:move=sysop]</p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<tr class="diff-title" lang="ja">
<td colspan="1" style="background-color: #fff; color: #202122; text-align: center;">← 古い版</td>
<td colspan="1" style="background-color: #fff; color: #202122; text-align: center;">2007年7月20日 (金) 02:09時点における版</td>
</tr><tr><td colspan="2" class="diff-notice" lang="ja"><div class="mw-diff-empty">(相違点なし)</div>
</td></tr></table>
Orsjwiki
https://orsj-ml.org/orwiki/wiki/index.php?title=%E3%83%9C%E3%83%AD%E3%83%8E%E3%82%A4%E5%9B%B3&diff=5152&oldid=prev
2007年7月17日 (火) 03:16に122.17.2.240による
2007-07-17T03:16:25Z
<p></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="ja">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← 古い版</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">2007年7月17日 (火) 03:16時点における版</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >1行目:</td>
<td colspan="2" class="diff-lineno">1行目:</td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>【ぼろのいず (Voronoi diagram)】</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">'''</ins>【ぼろのいず (Voronoi diagram)】<ins class="diffchange diffchange-inline">'''</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>空間に, 互いに共通部分をもたない有限個の図形を配置すると, それぞれの図形のまわりには他の図形より自分に近い点からなる領域が定まる. この領域をその図形のボロノイ領域という. 空間のボロノイ領域への分割をボロノイ図といい, はじめに配置された図形をこのボロノイ図の生成元という. 生成元, 距離, 空間の次元の選び方によってボロノイ図には多くの種類がある. ボロノイ図は, 勢力圏を表すものと解釈でき, 地理的最適化などに応用されている.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>空間に, 互いに共通部分をもたない有限個の図形を配置すると, それぞれの図形のまわりには他の図形より自分に近い点からなる領域が定まる. この領域をその図形のボロノイ領域という. 空間のボロノイ領域への分割をボロノイ図といい, はじめに配置された図形をこのボロノイ図の生成元という. 生成元, 距離, 空間の次元の選び方によってボロノイ図には多くの種類がある. ボロノイ図は, 勢力圏を表すものと解釈でき, 地理的最適化などに応用されている.</div></td></tr>
</table>
122.17.2.240
https://orsj-ml.org/orwiki/wiki/index.php?title=%E3%83%9C%E3%83%AD%E3%83%8E%E3%82%A4%E5%9B%B3&diff=4091&oldid=prev
122.17.2.240: 新しいページ: '【ぼろのいず (Voronoi diagram)】 空間に, 互いに共通部分をもたない有限個の図形を配置すると, それぞれの図形のまわりには他の図...'
2007-07-13T02:50:39Z
<p>新しいページ: '【ぼろのいず (Voronoi diagram)】 空間に, 互いに共通部分をもたない有限個の図形を配置すると, それぞれの図形のまわりには他の図...'</p>
<p><b>新規ページ</b></p><div>【ぼろのいず (Voronoi diagram)】<br />
<br />
空間に, 互いに共通部分をもたない有限個の図形を配置すると, それぞれの図形のまわりには他の図形より自分に近い点からなる領域が定まる. この領域をその図形のボロノイ領域という. 空間のボロノイ領域への分割をボロノイ図といい, はじめに配置された図形をこのボロノイ図の生成元という. 生成元, 距離, 空間の次元の選び方によってボロノイ図には多くの種類がある. ボロノイ図は, 勢力圏を表すものと解釈でき, 地理的最適化などに応用されている.</div>
122.17.2.240