複雜計算的Voronoi paritions

Question

我一直沒能找到谷歌搜索答案的，這就是爲什麼在這裏張貼：

什麼是對n維創建具有k中心點的Voronoi分區的時間複雜度？它是O（n^k）嗎？

謝謝。

Answer 1

你是什麼意思「創建分區」？ Voronoi單元由它們的質心定義，所以假設你知道中心點的局部化，「構造」需要O(n*k)時間（你必須在一些變量中存儲k個n維點）。現在，分配步驟在歐幾里得空間中的複雜度爲O（k * n），因爲您必須計算每個中心點的距離，並且在歐幾里得n維空間中花費O（n）時間。您可以通過使用一些地理索引技術來加快速度，這些技術將刪除不必考慮的點。