Voronoi図

平面上に複数の点(これを母点と呼びます)が与えられたとき、平面上の任意の点について最も近い母点を求めることができます。最も近い母点が同一となる点の集合を、その母点のVoronoi領域あるいは勢力圏と呼び、すべての母点のVoronoi領域で平面全体を分割することができます。この平面分割をVoronoi分割と呼びます。Voronoi(ボロノイ)図は、Voronoi領域およびその境界を表した図です。Voronoi図の名はロシアの数学者Georgy Voronoi(英語表記)にちなんだものです。
 Voronoi図は2次元平面に限らず、多次元のVoronoi図もあります。また、ユークリッド距離以外の距離に関しても、Voronoi図を作成することはできます。ユークリッド距離に基づく2次元Voronoi領域は、凸多角形となり、その頂点をVoronoi点と呼びます。Voronoi点は2つの母点を中心とした同じ半径の円の交点であり、Voronoi領域の境界線(凸多角形の辺)は各々の母点の垂直2等分線の一部です。
 Voronoi分割は、計算幾何学の重要なテーマであり、最近点問題(平面上の点の集合Pが与えられたとき、任意の点にもっとも近いPの点を求める問題)など、計算幾何学の多くの問題、特に各種の点の分布に関わる問題を効率的に解くために用いられています。Voronoi図は地理情報システムのさまざまな応用でも用いられています。最も典型的な利用例は、郵便局や郵便ポスト、駅やバス停などの施設の利用圏の同定です。これら施設の利用圏をVoronoi図で近似的に表現することで、施設の利用者を推定したり、施設を新設する際の参考にしたりすることができます。
 Voronoi図はDelaunay図の双対グラフであり、Delaunay図の代表的な定義はVoronoi図を利用したものです。

(2016年11月04日 初稿)

English

Voronoi diagram

定義

平面上に複数の点(これを母点と呼びます)が与えられたとき、最も近い母点が同一となる領域(点の集合)を、その母点のVoronoi領域といいます。すべての母点のVoronoi領域で平面全体を分割することをVoronoi分割といい、Voronoi分割の結果を図示したものがVoronoi(ボロノイ)図です。多次元のVoronoi図や、ユークリッド距離以外の距離に基づくVoronoi図もあります。