点集合 \(P=\{p_1,p_2,\ldots,p_n\}\) が与えられたとき,Voronoi図は空間を,各 \(p_i\) を含む,互いに素な領域に分割する.領域 \(p_i\) の領域は次式を満たす点 \(x\) の集合. \[\{x| d(x,p_i)\lt d(x,p_j),\;\forall\,j\ne i\}\] d() が Lp距離なら\(O(n \log n)\) の計算量. Dirichlet tessellationともいう.
-- しましま