高階ボロノイ図

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

${\rm P}_1, {\rm P}_2, \cdots , {\rm P}_n$ を平面上に配置された点とし, 平面上の任意の点 ${\rm P}$ と ${\rm P}_i$ の距離を $d({\rm P}, {\rm P}_i)$ とする.

\begin{eqnarray*} & \hspace*{-20mm} d({\rm P}, {\rm P}_{i_1})< d({\rm P}, {\rm P}_{i_2})< \cdots \\ & \hspace*{0mm} < d({\rm P}, {\rm P}_{i_k})< d({\rm P}, {\rm P}_j),\\ & \hspace*{20mm} 1 \leq j\leq n; \; j\ne 0, i_1, i_2, \cdots , i_k \end{eqnarray*}

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