我一直无法通过谷歌搜索找到答案，这就是为什么在这里发布它：
在n维中创建具有k个中心点的Voronoi分区的时间复杂度是多少？是O（n^k）吗？
谢谢。
"创建分区"是什么意思？Voronoi细胞是由它们的质心定义的，所以"构造"需要O(n*k)时间（你必须在一些变量中存储k，n维点），假设你知道中心点的定位。现在，在欧几里得空间中，赋值步骤的复杂性为O（k*n），因为你必须计算到每个中心点的距离，而在欧几里得n维空间中，它需要O（n）时间。你可以通过使用一些地理索引技术来加快速度，这些技术可以修剪不需要考虑的点。