Voronoi図 (Voronoi diagram)

点集合 \(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ともいう.

-- しましま

関連項目

リンク集

関連文献


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-02-11 (木) 16:11:27 (2487d)