复杂计算的Voronoi paritions

Question

我一直没能找到谷歌搜索答案的，这就是为什么在这里张贴：

什么是对n维创建具有k中心点的Voronoi分区的时间复杂度？它是O（n^k）吗？

谢谢。

Answer 1

你是什么意思“创建分区”？ Voronoi单元由它们的质心定义，所以假设你知道中心点的局部化，“构造”需要O(n*k)时间（你必须在一些变量中存储k个n维点）。现在，分配步骤在欧几里得空间中的复杂度为O（k * n），因为您必须计算每个中心点的距离，并且在欧几里得n维空间中花费O（n）时间。您可以通过使用一些地理索引技术来加快速度，这些技术将删除不必考虑的点。