Complexity of calculating Voronoi paritions

Question

I haven't been able to find an answer by Googling, that's why posting it here:

What's the time complexity for creating Voronoi partitions with k center points in n-dimension? Is it O(n^k)?

Thanks.

Answer 1

What do you mean by "creating a partition"? Voronoi cells are defined by their centroids, so the "construction" takes O(n*k) time (you have to store k, n dimensional points in some variables) assuming, that you know the localization of the center points. Now, the assignment step has a complexity of O(k*n) in Euclidean space, as you have to compute the distances from each of the center points, and in Euclidean n-dimensional space it takes O(n) time. You can speed things up by using some geo-indexing techniques which will prune the points which do not have to be considered.