ボロノイ図

数学において、ボロノイ図は、平面を、与えられた一連のオブジェクトのそれぞれに近い領域に分割したものです。これは、モザイク細分化としても分類できます。最も単純なケースでは、これらのオブジェクトは、平面内の有限個の点 (シード、サイト、またはジェネレータと呼ばれる) にすぎません。各シードには、ボロノイ セルと呼ばれる対応する領域があり、平面上の他のどの点よりもそのシードに近いすべての点で構成されます。点の集合のボロノイ図は、その集合のドロネー三角形分割と双対です。

ボロノイ図は数学者ゲオルギー・ボロノイにちなんで名付けられ、ボロノイ分割、ボロノイ分解、ボロノイ分割、ディリクレ分割（ピーター・グスタフ・ルジューヌ・ディリクレにちなんで）とも呼ばれる。ボロノイセルはアルフレッド・H・ティーセンにちなんでティーセン多角形とも呼ばれる。^{[1] [2] [3]ボロノイ図は、主に}科学技術分野で、また視覚芸術においても、多くの分野で実用的かつ理論的に応用されている。^{[4] [5]}

最初の図に示す最も単純なケースでは、ユークリッド平面上の有限の点の集合が与えられます。この場合、各点には、が最も近いサイト であるユークリッド平面 上の点からなる対応するセルがあります。つまり、 までの距離は、他のどのサイト までの最小距離以下です。他の 1 つのサイト について、よりも に近い点、または等距離にある点は、線分 の垂直二等分線を境界とする閉じた半空間を形成します。セル は、これらすべての半空間の交点であるため、凸多角形です。^[6]ボロノイ図の 2 つのセルが境界を共有する場合、それは線分、光線、または線であり、2 つの最も近いサイトから等距離にある平面内のすべての点で構成されます。これらの境界が 3 つ以上交わる図の頂点は、3 つ以上の等距離の最も近いサイトを持つ点です。 ${\displaystyle \{p_{1},\dots p_{n}\}}$${\displaystyle p_{k}}$${\displaystyle R_{k}}$${\displaystyle p_{k}}$${\displaystyle p_{k}}$${\displaystyle p_{j}}$${\displaystyle p_{j}}$${\displaystyle p_{k}}$${\displaystyle p_{j}}$${\displaystyle p_{j}p_{k}}$${\displaystyle R_{k}}$${\displaystyle n-1}$

を距離関数 を持つ距離空間とします。 をインデックスの集合とし、 を空間 内の空でない部分集合(サイト)の組(インデックス付きコレクション)とします。サイトに関連付けられたボロノイセル、またはボロノイ領域 は 、からの距離が他のサイト までの距離以下であるすべての点の集合です。ここで、 はとは異なるインデックスです。言い換えると、 が点と部分集合の間の距離を表す場合、 ${\textstyle X}$${\textstyle d}$${\textstyle K}$${\textstyle (P_{k})_{k\in K}}$${\textstyle X}$${\textstyle R_{k}}$${\textstyle P_{k}}$${\textstyle X}$${\textstyle P_{k}}$${\textstyle P_{j}}$${\textstyle j}$${\textstyle k}$${\textstyle d(x,\,A)=\inf\{d(x,\,a)\mid a\in A\}}$${\textstyle x}$${\textstyle A}$

$${\displaystyle R_{k}=\{x\in X\mid d(x,P_{k})\leq d(x,P_{j})\;{\text{すべて}}\;j\neq k\}}$$

ボロノイ図は、単にセルの組です。原理的には、サイトのいくつかは交差したり、一致したりすることさえできますが (店舗を表すサイトへの応用については以下で説明します)、通常は互いに素であると想定されます。さらに、定義では無限の数のサイトが許可されますが (この設定は数の幾何学や結晶学に応用されています)、この場合も、多くの場合、有限の数のサイトのみが考慮されます。 ${\textstyle (R_{k})_{k\in K}}$

空間が有限次元 ユークリッド空間であり、各サイトが点であり、有限個の点があり、それらすべてが異なるという特定のケースでは、ボロノイセルは凸多面体であり、頂点、辺、2次元面などを使用して組み合わせ的に表現できます。誘導された組み合わせ構造は、ボロノイ図と呼ばれることもあります。ただし、一般に、ボロノイセルは凸ではない場合や接続されていない場合さえあります。

通常のユークリッド空間では、正式な定義を通常の用語で書き直すことができます。各ボロノイ多角形は、生成点 に関連付けられています 。をユークリッド空間内のすべての点の集合とします。をボロノイ領域 を生成する点 、を生成し 、 を生成する点 などとします。すると、Tranら^[7]が表現したように、「ボロノイ多角形内のすべての位置は、ユークリッド平面のボロノイ図の他のどの生成点よりも、その多角形の生成点に近い」ことになります。 ${\textstyle R_{k}}$${\textstyle P_{k}}$${\textstyle X}$${\textstyle P_{1}}$${\textstyle R_{1}}$${\textstyle P_{2}}$${\textstyle R_{2}}$${\textstyle P_{3}}$${\textstyle R_{3}}$

簡単な例として、ある都市にある店舗群を考えてみましょう。特定の店舗の顧客数を推定したいとします。他の条件 (価格、製品、サービスの質など) が同じであれば、顧客は距離だけを考慮して好みの店舗を選ぶと想定するのが妥当です。つまり、最も近い店舗に行くのです。この場合、特定の店舗のボロノイ セルを使用して、この店舗 (都市内の 1 点によってモデル化されます) に行く潜在的顧客数を大まかに推定できます。 ${\displaystyle R_{k}}$${\displaystyle P_{k}}$

ほとんどの都市では、ポイント間の距離は、よく知られている ユークリッド距離を使用して測定できます。

${\displaystyle \ell _{2}=d\left[\left(a_{1},a_{2}\right),\left(b_{1},b_{2}\right)\right]={\sqrt {\left(a_{1}-b_{1}\right)^{2}+\left(a_{2}-b_{2}\right)^{2}}}}$

またはマンハッタン距離:

${\displaystyle d\left[\left(a_{1},a_{2}\right),\left(b_{1},b_{2}\right)\right]=\left|a_{1}-b_{1}\right|+\left|a_{2}-b_{2}\right|}$。

対応するボロノイ図は、距離メトリックによって見た目が異なります。

• ボロノイ図の双対グラフ(点群を持つユークリッド空間の場合) は、同じ点群のドロネー三角形分割に対応します。
• 最も近い点のペアは、ボロノイ図内の隣接する 2 つのセルに対応します。
• 設定がユークリッド平面であり、離散的な点の集合が与えられている場合、その集合の 2 つの点は、それらのボロノイ セルが無限に長い辺を共有する場合に限り、凸包上で隣接します。
• 空間がノルム空間であり、各サイトまでの距離が達成されている場合（たとえば、サイトがコンパクトセットまたは閉じた球である場合）、各ボロノイセルはサイトから発する線分の和集合として表すことができます。^[8]そこに示されているように、この特性は距離が達成されていない場合には必ずしも成り立ちません。
• 比較的一般的な条件（空間はおそらく無限次元の一様凸空間であり、一般的な形状のサイトは無限に存在する可能性がある、など）では、ボロノイセルは一定の安定性を備えています。つまり、サイトの形状がわずかに変化すると（たとえば、何らかの平行移動や歪みによって引き起こされる変化）、ボロノイセルの形状もわずかに変化します。これがボロノイ図の幾何学的安定性です。^[9]そこで示されているように、この特性は、空間が2次元（ただし一様凸ではなく、特に非ユークリッド）でサイトが点であっても、一般には成立しません。

ボロノイ図の非公式な使用は、1644年のデカルトにまで遡ります。^[10] ピーター・グスタフ・ルジューン・ディリクレは、 1850年に二次形式の研究で2次元および3次元のボロノイ図を使用しました。イギリスの医師ジョン・スノーは、 1854年にボロノイのような図を使用して、ブロードストリートのコレラ流行で亡くなった人の大半が、他のどの給水ポンプよりも感染したブロードストリートのポンプの近くに住んでいたことを説明しました。

ボロノイ図は、1908 年に一般的なn次元の場合を定義および研究したGeorgy Feodosievych Voronoyにちなんで名付けられました。 ^[11]地球物理学や気象学で空間的に分布したデータを分析するために使用されるボロノイ図は、1911 年に散在する測定から降雨量を推定するために使用したアメリカの気象学者Alfred H. Thiessenにちなんで、ティーセン多角形と呼ばれています。この概念 (または特定の重要な場合) には、ボロノイ多面体、ボロノイ多角形、影響領域、ボロノイ分解、ボロノイ分割、ディリクレ分割など、同義語もあります。

2 次元または 3 次元の点の 規則的な格子のボロノイ分割により、多くのよく知られた分割が生成されます。

• 2D 格子は、点対称の等しい六角形を持つ不規則なハニカム タイル分割を生成します。正三角形格子の場合は正則です。長方形格子の場合は、六角形が行と列の長方形に縮小されます。正方格子は、正方形の規則的なタイル分割を生成します。長方形と正方形は、他の格子によっても生成できることに注意してください (たとえば、ベクトル (1,0) と (1/2,1/2) によって定義される格子は正方形を生成します)。
• 単純な立方格子は立方ハニカム構造を形成します。
• 六方最密格子は、台形菱形十二​​面体による空間のモザイク状配置を与えます。
• 面心立方格子は、菱形十二面体による空間のモザイク化を実現します。
• 体心立方格子は、切頂八面体による空間のモザイク化を実現します。
• 互いの中心を揃えた正三角形の格子を持つ平行平面が、六角柱状のハニカムを形成します。
• 特定の体心四方格子は、菱形六角形十二面体による空間のモザイク状配置を与えます。

特定の体心四方格子は、菱形六角形十二面体による空間のモザイク状配置を与えます。

離散集合X内のxと離散集合Y内のyを持つ点の集合 ( x、  y )の場合、点が必ずしも中心にあるとは限らない長方形のタイルが得られます。

通常のボロノイセルはS内の単一の点に最も近い点の集合として定義されますが、n次のボロノイセルはS内の特定のn点の集合をn近傍として持つ点の集合として定義されます。高次のボロノイ図も空間を細分化します。

高次のボロノイ図は再帰的に生成できます。集合 Sからn^次のボロノイ図を生成するには、 ( n  − 1)^{次の図から始めて、} X  = { x ₁、  x ₂、 ...、  x _{n −1} }によって生成された各セルを集合 S  −  X上に生成されたボロノイ図に置き換えます。

n個の点の集合に対して、( n  − 1)^次のボロノイ図は最遠点ボロノイ図と呼ばれます。

与えられた点の集合S  = { p ₁ ,  p ₂ , ...,  p _n } について、最遠点ボロノイ図は、Pの同じ点が最遠点となるセルに平面を分割します。 Pの点が最遠点ボロノイ図にセルを持つのは、それがPの凸包の頂点である場合のみです。H  = { h ₁ ,  h ₂ , ...,  h _k } をPの凸包とします。すると、最遠点ボロノイ図は平面をk 個のセルに分割したもので、各セルはHの各点に対応し、点qがサイトh _iに対応するセル内にあるのは、各p _j  ∈  Sにおいてh _i ≠ p _jに対してd( q , h _i ) > d( q , p _j )が成立する場合のみであるという性質を持つ。ここで d( p , q ) は2 点pと q間のユークリッド距離である。^{[12] [13]}

最遠点ボロノイ図のセル境界は、無限の光線を葉とする位相木の構造を持つ。すべての有限木は、最遠点ボロノイ図からこのように形成された木と同型である。^[14]

定義からわかるように、ボロノイセルは、マハラノビス距離やマンハッタン距離など、ユークリッド以外の測定基準に対しても定義できます。ただし、これらの場合、2 次元の場合でも、2 つの点の等距離軌跡が余次元 1 の部分空間にならない可能性があるため、ボロノイセルの境界はユークリッドの場合よりも複雑になる可能性があります。

重み付きボロノイ図は、ボロノイセルを定義する2点の関数が、生成点に割り当てられた乗法または加算の重みによって修正された距離関数である図です。距離 （メトリック）を使用して定義されたボロノイセルの場合とは対照的に、この場合はボロノイセルの一部が空になることがあります。べき乗図は、べき乗距離を使用して円の集合から定義されたボロノイ図の一種です。また、各円の半径から定義された重みが円の中心からのユークリッド距離の2乗に追加された重み付きボロノイ図と考えることもできます。^[15]

次元空間の点のボロノイ図には頂点が存在する可能性があり、明示的な記述を格納するために必要なメモリ量に同じ制限が課せられる。そのため、ボロノイ図は中次元または高次元では実現できないことが多い。よりスペース効率の良い代替手段は、近似ボロノイ図を使用することである。^[16]${\displaystyle n}$${\displaystyle d}$${\textstyle O(n^{\lceil d/2\rceil })}$

ボロノイ図は、中心軸(画像セグメンテーション、光学式文字認識、その他の計算アプリケーションで応用されています)、直線スケルトン、ゾーン図などの他の幾何学的構造にも関連しています。

これは気象学や工学水文学において、ある地域（流域）の観測所の降水量データの重みを求めるために使用されます。多角形を生成するポイントは、降水量データを記録するさまざまな観測所です。任意の 2 つの観測所を結ぶ線に垂直な二等分線が引かれます。これにより、観測所の周囲に多角形が形成されます。観測所ポイントに接するエリアは、観測所の影響エリアと呼ばれます。平均降水量は、次の式で計算されます。${\displaystyle (A_{i})}$${\displaystyle {\bar {P}}={\frac {\sum A_{i}P_{i}}{\sum A_{i}}}}$

• 古典考古学、特に美術史では、彫像の頭部の対称性を分析して、切断された頭部がどのタイプの彫像のものであったかを判断します。ボロノイセルを使用した例としては、サブロフの頭部の識別が挙げられ、高解像度のポリゴンメッシュが使用されました。^{[17] [18]}
• 方言測定学では、ボロノイセルは調査点間の想定される言語の連続性を示すために使用されます。
• 政治学では、ボロノイ図は多次元の多党間競争を研究するために使われてきました。^[19]

• 生物学では、ボロノイ図は細胞^[20]や骨の微細構造^[21]を含むさまざまな生物学的構造をモデル化するために使用されています。実際、ボロノイ分割は、生物学的組織の組織化を推進する物理的制約を理解するための幾何学的ツールとして機能します。^[22]
• 水文学では、ボロノイ図は一連の点の測定に基づいて、ある地域の降雨量を計算するために使用されます。この用法では、ボロノイ図は一般にティーセン多角形と呼ばれます。
• 生態学では、ボロノイ図は森林や森林冠の成長パターンを研究するために使用され、森林火災の予測モデルの開発にも役立つ場合があります。
• 動物行動学では、ボロノイ図は利己的な群れの理論における危険領域をモデル化するために使用されます。
• 計算化学では、リガンド結合部位は機械学習アプリケーション（例えば、タンパク質の結合ポケットを分類するため）のためにボロノイ図に変換されます。^[23]他のアプリケーションでは、分子内の核の位置によって定義されるボロノイセルが原子電荷を計算するために使用されます。これは、ボロノイ変形密度法を使用して行われます。
• 天体物理学では、ボロノイ図を使用して画像上に適応的な平滑化ゾーンを生成し、各ゾーンに信号フラックスを追加します。これらの手順の主な目的は、すべての画像で比較的一定の信号対雑音比を維持することです。
• 計算流体力学では、点の集合のボロノイ分割は、例えば移動メッシュ宇宙論コードAREPOなどの有限体積法で使用される計算領域を定義するために使用することができます。 ^[24]
• 計算物理学では、ボロノイ図はシャドウグラフや高エネルギー密度物理学における陽子放射線写真法を用いて物体のプロファイルを計算するために使用されます。^[25]

• 医療診断では、ボロノイ図に基づいた筋組織のモデルを使用して神経筋疾患を検出することができます。^[22]
• 疫学では、ボロノイ図は伝染病の感染源の相関関係を調べるのに使われます。ボロノイ図の初期の応用例の1つは、ジョン・スノーが1854年にイギリスのソーホーで起きたブロードストリートのコレラ流行を研究するために実装したものです。彼はロンドン中心部の地図上で、住民が特定の給水ポンプを使用していた居住地域と、流行による死者数が最も多かった地域との相関関係を示しました。^[26]

• 高分子物理学では、ボロノイ図を使用してポリマーの自由体積を表すことができます。
• 材料科学では、金属合金の多結晶微細構造は、通常、ボロノイ分割を使用して表現されます。
• 島の成長においては、ボロノイ図は個々の島の成長率を推定するために使用される。^{[27] [28] [29] [30] [31]}
• 固体物理学では、ウィグナー・ザイツセルは固体のボロノイ分割であり、ブリルアンゾーンは空間群の対称性を持つ結晶の逆数（波数）空間のボロノイ分割です。
• 航空業界では、航空機が飛行計画に沿って飛行する際に、飛行中の迂回（ETOPSを参照）に最も近い飛行場を特定するために、ボロノイ図が海洋図に重ね合わされます。
• 建築分野では、ボロノイパターンはゴールドコースト・アートセンターの再開発における優勝作品の基礎となった。^[32]
• 都市計画では、ボロノイ図は貨物積載ゾーンシステムの評価に使用できます。^[33]
• 鉱業では、ボロノイ多角形は貴重な材料、鉱物、またはその他の資源の埋蔵量を見積もるために使用されます。探査用の掘削孔は、ボロノイ多角形の点の集合として使用されます。
• 表面計測学では、ボロノイ分割法を用いて表面粗さのモデリングを行うことができる。^[34]
• ロボット工学では、マルチロボットシステムの制御戦略と経路計画アルゴリズム^[35]のいくつかは、環境のボロノイ分割に基づいています。^{[36] [37]}

• ボロノイ図の上にポイント位置データ構造を構築することで、最近傍クエリに答えることができます。最近傍クエリでは、特定のクエリ ポイントに最も近いオブジェクトを見つけます。最近傍クエリにはさまざまな用途があります。たとえば、最も近い病院や、データベース内で最も類似したオブジェクトを見つけたい場合があります。大きな用途は、データ圧縮でよく使用されるベクトル量子化です。
• 幾何学では、ボロノイ図は、点の集合の中やそれを囲む多角形の中で最大の空の円を見つけるために使用できます。たとえば、ある都市にある既存のスーパーマーケットからできるだけ離れた場所に新しいスーパーマーケットを建設する場合などです。
• ボロノイ図は最遠点ボロノイ図とともに、点の集合の真円度を計算する効率的なアルゴリズムに使用されます。 ^{[12]ボロノイアプローチは、}座標測定機からのデータを評価する際に、真円度/真円度を評価する際にも使用されます。
• 複素平面上の有理関数の反復導関数の零点は、極集合のボロノイ図の辺に蓄積される（ポリアのシャイア定理^[38]）。

• ネットワークでは、ボロノイ図はワイヤレス ネットワークの容量の導出に使用できます。
• コンピュータグラフィックスでは、ボロノイ図は 3D の粉砕/破砕ジオメトリ パターンを計算するために使用されます。また、有機的または溶岩のようなテクスチャを手順的に生成するためにも使用されます。
• 自律ロボットナビゲーションでは、明確なルートを見つけるためにボロノイ図が使用されます。ポイントが障害物である場合、グラフのエッジは障害物（および理論的には衝突）から最も遠いルートになります。
• 機械学習では、ボロノイ図は1-NN分類を行うために使用されます。^[39]
• ランダムなセンサーサイトや非定常な後流、地球物理学的データ、3D乱流データを含む地球規模のシーン再構築では、ボロノイ分割がディープラーニングで使用されます。^[40]
• ユーザーインターフェースの開発では、ボロノイパターンを使用して、特定のポイントに最適なホバー状態を計算することができます。^[41]

ボロノイ図を直接的に（図自体として）構築する方法と、ドロネー三角形分割から始めてその双対を求めることによって間接的に構築する方法の、効率的なアルゴリズムがいくつか知られている。直接的なアルゴリズムには、平面上の点の集合からボロノイ図を生成する O ( n log( n )) アルゴリズムであるフォーチュンのアルゴリズムがある。任意の次元数のドロネー三角形分割を生成する O ( n log( n ) )からO ( n 2 ) アルゴリズムであるボウヤー・ワトソンアルゴリズムは、ボロノイ図の間接的なアルゴリズムに使用できる。ジャンプフラッディングアルゴリズムは、定数時間で近似^ボロノイ図を生成でき、市販のグラフィックスハードウェアでの使用に適している。^{[42] [43]}

ロイドのアルゴリズムと、リンデ・ブゾ・グレイアルゴリズムによるその一般化（別名k-means クラスタリング）では、ボロノイ図の構築をサブルーチンとして使用します。これらの方法では、シードポイントのセットに対してボロノイ図を構築するステップと、シードポイントをセル内のより中心となる新しい場所に移動するステップが交互に実行されます。これらの方法は、任意の次元の空間で使用して、重心ボロノイ分割と呼ばれるボロノイ図の特殊な形式に反復的に収束させることができます。この形式では、サイトはセルの幾何学的中心でもあるポイントに移動されます。

Voronoi メッシュは 3D でも生成できます。

• 
  3Dボロノイ分割を形成するための3Dのランダムポイント
• 
  25 個のランダムな点からなる 3D ボロノイ メッシュ
• 
  0.3の不透明度と点を持つ25個のランダムな点の3Dボロノイメッシュ
• 
  25 個のランダムな点と凸多面体の 3D ボロノイ メッシュ

ウィキメディア・コモンズには、ボロノイ図に関連するメディアがあります。

• ワイスタイン、エリック W.「ボロノイ図」。マスワールド。
• 計算幾何学アルゴリズムライブラリCGALのボロノイ図
• ステップ火災モデルを使用してボロノイ図を作成する SFTessellation アルゴリズムのデモ プログラム