ティーセン法

ウィキペディア

ボロノイ図

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/02/08 08:21 UTC 版)

ボロノイ図の一例 個々の色分けが一つの領域を表す

ボロノイ図 （ボロノイず、英: Voronoi diagram）は、ある距離空間上の任意の位置に配置された複数個の母点（英: site、サイト）に対して、同一距離空間上の他の点がどの母点に近いかによって領域分けされた図のことである。特に二次元ユークリッド平面の場合、領域の境界線は、各々の母点の二等分線の一部になる。母点の位置のみによって分割パターンが決定されるため、母点に規則性を持たせれば美しい図形を生み出すことが可能。

定義

距離空間 (X, d) 内の有限な部分集合 P ⊂ X が与えられたとき、各点 p ∈ P を母点またはサイトと呼び、これに対して、X の中で「P の点の中で p が最も近い」点の集合

$V(p)=\{x\in X\mid \forall q\in P\;[d(x,p)\leq d(x,q)]\}$

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

• ドロネー図
• 離散ボロノイ図
• 最近傍探索

脚注

文献

日本語

• J. マトウシェク 著、岡本 吉央 訳『離散幾何学講義』シュプリンガー・フェアラーク東京、2005年11月26日（原著2002年）。ISBN 4-431-71041-8。 

外国語

外部リンク

• 『ボロノイ図とその３つの性質』 - 高校数学の美しい物語