ボロノイ図

数学において、ボロノイ図とは、与えられた一連の対象物それぞれに近い領域に平面を分割したものです。これはテセレーション（平面充填）の一種とも言えます。最も単純な場合、これらの対象物は平面上の有限個の点（シード、サイト、またはジェネレーターと呼ばれる）です。各シードには対応する領域があり、これはボロノイセルと呼ばれ、平面上の他のどのシードよりもそのシードに近いすべての点から構成されます。点の集合のボロノイ図は、その集合のドロネー三角形分割と双対関係にあります。

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

最初の図に示す最も単純なケースでは、有限個の点が与えられます。${\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}$半空間であるため、凸多角形です。^{[ 6 ]}ボロノイ図の 2 つのセルが境界を共有する場合、それは線分、光線、または直線であり、それらの最も近い 2 つのサイトから等距離にある平面上のすべての点から構成されます。これらの境界が 3 つ以上交わる図の頂点は、3 つ以上の等距離の最近接サイトを持つ点です。

させて${\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次元面などを用いて組み合わせ的に表現できます。この組み合わせ構造は、ボロノイ図と呼ばれることもあります。しかし一般に、ボロノイセルは凸であるとは限らず、連結しているとは限りません。

通常のユークリッド空間では、形式的な定義を通常の用語で書き直すことができます。各ボロノイ多角形${\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}}$など。そして、Tranら[ ^{7 ]が述べているように、「ボロノイ多角形内のすべての位置は、ユークリッド平面上のボロノイ図内の他のどの生成点よりも、}その多角形の生成点に近い」。

簡単な例として、ある都市にある複数の店舗を考えてみましょう。特定の店舗の顧客数を推定したいとします。価格、商品、サービスの質など、他の条件がすべて同じであれば、顧客は距離を考慮して好みの店舗を選ぶと考えるのが妥当です。つまり、最も近い店舗に行くでしょう。この場合、ボロノイセルは${\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つの異なる指標に基づく20点のボロノイ図

ユークリッド距離

マンハッタンまでの距離

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

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

ボロノイ図は、 1908 年に一般的なn次元の場合を定義し研究したGeorgy Feodosievych Voronoyにちなんで名付けられました。 ^{[ 11 ]}地球物理学や気象学で空間的に分布したデータを分析するために使用されるボロノイ図は、1911 年に散在する測定値から降雨量を推定するためにこれらを使用したアメリカの気象学者Alfred H. Thiessenにちなんで、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で生成されたボロノイ図に置き換えます。           

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

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

ボロノイ図${\displaystyle n}$ポイント${\displaystyle d}$次元空間は${\textstyle O(n^{\lceil d/2\rceil })}$頂点の数が同じであるため、明示的な記述を格納するために必要なメモリ量に同じ上限が必要になります。したがって、ボロノイ図は中次元または高次元では実行不可能な場合が多いです。よりスペース効率の良い代替案は、近似ボロノイ図を使用することです。^{[ 16 ]}

ボロノイ図は、メディアル軸（画像分割、光学文字認識、その他の計算アプリケーションで応用されている）、直線骨格、ゾーン図などの他の幾何学的構造とも関連しています。

ボロノイ図を構築するための効率的なアルゴリズムはいくつか知られており、直接（図自体として）構築する方法と、ドロネー三角形分割から始めてその双対を求める間接的な方法があります。直接的なアルゴリズムには、平面上の点の集合からボロノイ図を生成する O ( n log( n ))アルゴリズムであるFortuneのアルゴリズムがあります。任意の^{次元でドロネー三角形分割を生成する}O ( n log( n ))からO ( n² )アルゴリズムであるBowyer–Watsonアルゴリズムは、ボロノイ図の間接的なアルゴリズムで使用できます。

離散グリッド近似（ピクセルレンダリングなど）には、ジャンプフラッディングアルゴリズム（JFA）とその派生アルゴリズムが、汎用グラフィックスハードウェア（ GPU ）で広く使用されています。2006年にRong Guodongによって最初に導入された標準JFAは、近似ボロノイ図を計算します。${\displaystyle O(\log N)}$平行パス${\displaystyle N\times N}$グリッド。^{[ 42 ] [ 43 ]} Maciej A. Czyzewski によって導入された2019 年のランダム化JFA-starバリアントなどのその後の最適化では、パスの複雑さがグリッド解像度に応じてスケーリングされることから、シードポイントの総数 (${\displaystyle n}$）より速い収束を約${\displaystyle O(\log ^{*}n)}$合格。^{[ 44 ]}

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

ボロノイメッシュは3Dでも生成できる。

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

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