数学では、ボロノイ図(ロシアの数学者ゲオルギ・フェドセービッチ・ボロノイ (1868 ～ 1908) にちなんでボロノイ分解またはボロノイ分割とも呼ばれる) は、空間内のオブジェクトの離散セットまでの距離によって決定される計量空間の特定の分解であり、一般的には離散的な点の集合。
意味
私たちは自分自身をユークリッド空間Eに置きます。 S をEのn点の有限集合とする。 Sの要素は、センター、サイト、またはシードとさえ呼ばれます。
Sの要素pに関連付けられた、 Sの他の点よりも p に近い点のセットをボロノイ領域またはボロノイ セルと呼びます。
Sの 2 つの点aおよびbについて、 aおよびbから等距離にある点の集合Π( a , b )はアフィン超平面(共次元 1 のアフィン部分空間) です。この超平面は、 bよりもaに近い点のセットと、 aよりもbに近い点のセットの間の境界です。
H(a,b)はa を含むこの超平面によって区切られた半空間であり、この超平面にはbよりもaに近いすべての点が含まれます。 aに関連付けられたボロノイ領域は、 b がS\{a}を横切るH(a,b)の交差点になります。
ボロノイ領域は、半空間の交差点として凸状の多面体です。このようなポリゴンのセットは E を分割し、セットSに対応するボロノイ パーティションになります。
次元2 では、これらのパーティションを描くのは簡単です。この場合、それらはボロノイ図と呼ばれることもあります。我々はこれを、2 つの異なる細菌のボロノイ細胞間の境界が必然的にこれら 2 つの細菌を隔てるメディエーター上に位置するという事実に基づいています。実際、この二等分線の点は 2 つのシードから等距離にあるため、どちらかのボロノイ セルに位置するとは言えません。したがって、ジャームのセットについては、ジャームの各ペアの二等分線を決定することによってボロノイ図が構築されます。二等分上の点が少なくとも 2 つのシードから等距離にあり、この点とセット内の別のシードの間にこれ以上の距離がある場合、その点はボロノイ境界に属します。
ボロノイ図は ドロネー三角形分割の双対であり、ボロノイ図からドロネー三角形分割を定義できます。2 つの点 p と q は、p と q に関連付けられたボロノイ領域が隣接している場合に限り、ドロネーグラフにエッジを作成します。
歴史
ボロノイ図の非公式な使用は、1644 年のデカルトにまで遡ります。ディリクレは、1850 年の二次形式の研究で 2 次元または 3 次元のボロノイ図を使用しました。
英国の物理学者ジョン・スノーは、1854 年にボロノイ図を使用して、ソーホー州のコレラ流行で死亡した人の大多数が、他のどのポンプよりも感染したブロードストリートのポンプの近くに住んでいることを示しました。
ボロノイ図は、1908 年に次元 n の一般的なケースを定義および研究したロシアの数学者ゲオルギー フェドセーヴィチ ボロノイ (またはボロノイ) にちなんで名付けられました。 空間分布データ(降雨量測定など) を分析するために地球物理学および気象学で使用されるボロノイ図は、ティーセンと呼ばれますアメリカの気象学者アルフレッド・H・ティーセンにちなんだポリゴン。
例
次の例では、ドロネー三角形分割の例と同じ点を使用します。 
アルゴリズム
Steven Fortune のアルゴリズム(1987、 Bell AT&T Laboratories) は最適であることが実証されており、 n時点のセットのボロノイ図O ( n log( n ))を計算することができます。
アプリケーション
ボロノイ図はさまざまな分野で使用されたり、さまざまな名前で再発明されたりしています。これらは、空間を影響範囲に分割しようとするときによく機能します。