距離を変えたボロノイ

「近さ」の物差しを L1・L∞・重み付きに替えると、同じ母点から別のボロノイ図が出る。L1 では境界の向きが決まった角度に限られるが、隣接関係の9割は L2 と同じで、島が出るのは重み付きだけである。

同じ40点を4つの距離で分割した藍色のボロノイ図が2×2に並ぶ。左上は碁盤の道のり（辺が0°45°90°）、右上はユークリッド、左下は王将の歩数、右下は乗法重みで円弧の島がある — 同じ 40 点を 4 つの物差しで分割した。左上が L1（碁盤の道のり）、右上が L2（ユークリッド）、左下が L∞（王将の歩数）、右下が乗法重み（距離 ÷ w）。重みのときだけ円弧の「島」が出る。

なにか

ボロノイ図は「いちばん近い母点はどれか」で平面を分ける。その「近い」の物差しを取り替えると、同じ点の並びから別の地図が出てくる。碁盤の目の街の道のり（L1）、王将の歩数（L∞）、その間の Lp、それに母点ごとの重み（強い母点ほど遠くまで縄張りを広げる）。計算はラスタで、各マスから全母点までの距離を測って最小を取るだけなので、物差しが何であっても手順は変わらない。

境界は量子化し、隣は変わらない

4つの距離の分割図と、境界の向きの割合の表、Lpのpを振ったときの隣接の一致率と量子化した境界の割合のグラフ — 上は 4 つの分割。下は境界の向きの割合（0°・45°・90°・135°・その他）と、Lp の p を 1 から 40 まで振ったときの、L2 との隣接の一致率および 45° に量子化した境界の割合。

境界の向きは物差しで量子化する。境界画素の向きを 7 画素の窓で推定すると、0°・45°・90°・135° に乗るのは L1 で 77%、L∞ で 81%。L2 は 36% で、残りはあらゆる向きに散らばる。L1 では 2 点の等距離線が水平と垂直と 45° の折れ線だけでできているからだ。ところが「誰と隣か」、つまり隣接グラフは、L2 と L1 で 0.89、L∞ で 0.88 一致する。物差しは境界の形を作り替えるのに、隣は 9 割そのまま残る。Lp の p を 1 から 40 まで振ると、隣接の一致率は p=2 を頂点になだらかに下がり、量子化した境界の割合は逆に p=2 を底にして上がっていく（1 と ∞ でどちらも 74%）。

「島」が出るのは乗法重みだけだった。重み w を 0.5〜2.0 の乱数で振ると、切れたセルが 3 つ、隣がひとつしかない囲まれたセルが 1 つ現れる。L1・L2・L∞ ではセルはどれもつながっていて、囲まれるものはない。重みつきの等距離線は円弧（Apollonius の円）になるので、弱い母点の縄張りは強い母点の中に丸く閉じ込められてしまう。内側のセルの隣接数の平均は L1・L2・L∞ で 5.9〜5.8、オイラーの 6 の前後に収まる。重みつきだけは囲まれたセルのぶん 4.9 に下がる。

別の道からも確かめた。L∞ は L1 を 45° 回したものなので、母点を 45° 回して L1 で分割してやれば L∞ の地図と重なるはずで、実際 100.0% のマスで一致した。
気をつける点が三つ。ラスタは 240² で、向きの推定は 7 画素の窓を使うから、セルの角の近くでは「その他」に落ちる。L1 でも量子化率が 100% にならないのはそのためで、道具の限界であって物差しの性質ではない。島の数は重みの散らばり次第で変わる。

呼び名を調べたら、同じ「Apollonius」が正反対の変種に当てられていた。ここで使ったのは乗法の重み（|x − p| ÷ w）で、等距離線が Apollonius の円になるのはこちらである。Aurenhammer と Klein の総説も乗法の重みを「the Apollonius model」と呼び、加法の重みは「the Johnson-Mehl model」と呼んでいる。ところが CGAL のマニュアルは、加法の重み δ(x, P_i) = ‖x − c_i‖ − w_i による分割を「Apollonius diagram、別名 additively weighted Voronoi diagram」と定義している。どちらか一方を「Apollonius 図」と書くと、別の本を開いた読者が迷う。

power 図のほうは食い違いがない。Aurenhammer が 1987 年の論文（SIAM J. Comput. 16 の 78 ページから）で距離を d(x, p)² − w(p) と置き、p.79 で「power diagram」と名づけて、Laguerre diagram と Dirichlet cell complex を同義語として併記している。ここで作ったのは乗法の重みなので、power 図そのものは作っていない。Okabe ほかの教科書は貸出制限で開けなかったので、出典から外した。

→ ボロノイ図（L2・平均 6 の出どころ）

→ 双曲ボロノイ（空間を変えると「平均 6」が壊れる）

→ 詰まり方の帳簿（セルの辺の数と面積の関係）

どう作ったか

生成器は generators/voronoi-metric.js で、ラスタ 240²（出荷図は 250²）の上で全母点との距離の最小を記録していく。そこから境界・隣接・連結成分・向きを帳簿にした。同じ地図を 2 通りに作って突き合わせる手も入れてあり、L∞ の地図は、母点を 45° 回して L1 で分割したものと重なる。

出典

数理: G. Voronoi (1908)／F. Aurenhammer, "Power diagrams: properties, algorithms and applications", SIAM J. Comput. 16 (1987), 78–96＝power 図の定義は p.79／F. Aurenhammer, R. Klein, "Voronoi diagrams"（Handbook of Computational Geometry）＝乗法の重みを「Apollonius model」、加法を「Johnson–Mehl model」と呼ぶ箇所／CGAL, "2D Apollonius Graphs" のマニュアル＝加法の重みを「Apollonius diagram」と呼ぶ箇所。数字はすべて自分のラスタで測った
親戚: ボロノイ図・双曲ボロノイ・ボロノイ×Hat・詰まり方の帳簿・スーパー楕円（Lp の単位円）
生成: generators/voronoi-metric.js（voronoi-metric.svg 4 分割・voronoi-metric-book.svg 帳簿）