ボロノイ図いろいろ

Webエンジニアバトルロワイヤルでは、平面分割手法としてボロノイ図と「疑似築道法」というものをデモしたんですが、そのとき説明に使った4種類の2次元ボロノイ図を以下に載せます。

通常のボロノイ図

「どの母点が最も近くにあるか」にもとづいて平面を分割します。ボロノイ辺は母点の垂直二等分線になります。

マンハッタン距離にもとづくボロノイ図

ユークリッド距離の代わりにマンハッタン距離を使うと、見た目ががらっと変わって、路線図や天気予報のときの都道府県図っぽくなります。

加法的重み付きボロノイ図 (Additively Weighted Voronoi Diagram)

母点にそれぞれ重みを設定して、ユークリッド距離に重みを加算したものを距離関数としてボロノイ図を作ると、ボロノイ領域を膨らませたり縮ませたりできます。ボロノイ辺は双曲線になります。

加法的重み付きべき乗ボロノイ図 (Additively Weighted Power Voronoi Diagram)

上と似ていますが、ユークリッド距離の二乗に重みを加算したものを距離関数にすると、ボロノイ辺は直線になります。Blogopolisで使っているのがこれです。

重み付きボロノイ図の場合、ボロノイ領域の中に母点が含まれる保証はありません。また、領域が消えてしまうこともあります（どの位置からも最短距離では到達できない母点が出てくる）。