ボロノイ図とは

ボロノイ図はある平面に複数の点(サイトと呼ぶ.)がばら撒かれているときにそれらの点のどこに最も近いかで領域を分割している図形のこと. 様々なアプリケーションで用いることができ、ネットワーク、CG、医療、環境、建築など複数の分野で活用されている. ボロノイ図の幾何的特徴 ・ボロノイ図の頂点数は高々2n-5 ・ボロノイ図の辺数は高々3n-6 ・ボロノイ図の辺(ボロノイ辺)は隣接点同士の二等分線

よく見られるのはユークリッド距離によって距離を計算して求めるボロノイ図形であるが、 これをマンハッタン距離に置き換えられたものなどもある.