Fast way to compute the Voronoi diagram knowing the k-nearest neighbours

Question

I know it is relatively easy to compute the sets of k-nearest neighbours from a Voronoi tessellations. What about the reverse problem? I already have the set of k-nearest neighbours (in 3D) and I would like to compute the volumes and centres of the Voronoi cells. Intuitively, there should be an O(n) algorithm that does that, right?

Has anyone seen something like this implemented somewhere?

Thanks in advance

PS: I assume that no Voronoi cell has more than k edges (this prior knowledge on the location of the points is probably what makes it possible to compute the diagram in O(n), independently of the dimensionality).

PPS: I further assume that for a given point, the vertices of the Voronoi cell belong to the set of kNN (see comments below).

Answer 1

You can build the VD as follows. A point P and one of its k nearest neighbors Q define a half-plane H(P,Q) equidistant to both P and Q, and a half-space H+(P,Q) with boundary H and containing P. Then the Voronoi cell of P is the intersection of the H+(P,Q) for all Q in the k nearest neighbors of P. Building this intersection is very closely related to the Vertex Enumeration Problem: http://en.wikipedia.org/wiki/Vertex_enumeration_problem

You need to have enough neighbors to be sure that the correct VD is constructed and I'm not sure that your assumptions guarantee that. The only sure thing is that the real Voronoi cell of a point P is included in the cell that the algorithm above constructs.