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.

Answer 2

While there should be an intuitive algorithm, I don't think that there actually is one. While I have no formal proof (and couldn't make one up that fast), consider the following argument:

Consider the case where the k-nearest neighbouring points K of a point P are all to one side of P, i.e. there is a plane through P such that all points in K are on one side of the plane. The boundary of the Voronoi cell of P can then not be computed, in any way, from the points in K. This argument holds for any k, and I can't see any way how an algorithm could detect the presence of any point on the other side of P by nearest-neighbour analysis. Therefore, I argue that the Voronoi diagram contains more information than the k-nearest neighbours statistic and therefore the transformation from Voronoi to kNN is an irreversible reduction.

On the other hand, Hugo Ledoux has developed a n log n average case algorithm for Voronoization, you might consider that solution.

Edit: My argument is probably still too complex. Simple thought about kNN: Consider a cluster of k points that are the kNN to each other. The kNN subgraph for these points is disconnected from all other points, making the construction of a Voronoi diagram impossible. Or, in other terms, the Voronoi diagram contains the k-nearest neighbours for any k, thus cannot be reconstructed from any finite k.