高階ボロノイ図

【こうかいぼろのいず (higher-order Voronoi diagram) 】

$\mathrm {P} _{1},\mathrm {P} _{2},\cdots ,\mathrm {P} _{n}\,$ を平面上に配置された点とし, 平面上の任意の点 $\mathrm {P} \,$ と $\mathrm {P} _{i}\,$ の距離を $d(\mathrm {P} ,\mathrm {P} _{i})\,$ とする.

${\begin{array}{l}d(\mathrm {P} ,\mathrm {P} _{i_{1}})<d(\mathrm {P} ,\mathrm {P} _{i_{2}})<\cdots \\\ \ \ <d(\mathrm {P} ,\mathrm {P} _{i_{k}})<d(\mathrm {P} ,\mathrm {P} _{j}),\\1\leq j\leq n\ j\neq 0,i_{1},i_{2},\cdots ,i_{k}\end{array}}\,$

を満たす点 $\mathrm {P} \,$ 全体がなす領域を$(\mathrm {P} _{i_{1}},\mathrm {P} _{i_{2}},\cdots ,\mathrm {P} _{i_{k}})\,$ の $k\,$ 階ボロノイ領域という. 平面を $k\,$ 階ボロノイ領域とその境界に分割した図形を, $k\,$ 階ボロノイ図という.