Associating simplices from triangulation of natural neighbor circumcenters with Voronoi polytopes

Question

Given a set X of data points in n-dimensions, for which I have computed the Delaunay triangulation (DT0), and the circumcenters of the simplices of the triangulation. I want to compute the Voronoi tessellation of X. As I understand it, a triangulation of the Voronoi polytope for a single point x in X can be obtained by triangulating the circumcenters of the natural neighbor simplices of which x is a vertex.

But can this be done in bulk? Suppose I compute DT1, the triangulation of all the circumcenters of all the simplices in DT0. Is there an efficient method to then match the simplices of DT1 with individual points from X, to separate the Voronoi polytopes? One slow method would be to calculate, for each simplex in DT1, the centroid, and find the closest data point x. The Voronoi polytope of x is the union of the set of simplices whose centroids are closer to x than to any other data point.

Reiterating to clarify: my question assumes that we have already computed the Delaunay triangulation of all the centers of the circumspheres of the simplices resulting from the Delaunay triangulation of the original data. Starting from that second triangulation (and not from the convex hull of a local triangulation around x), of all the circumcenters, can its triangles be efficiently identified to the Voronoi polytopes?

Answer 1

Delaunay triangulation (or Delaunay complex) and Voronoi complex are vice versas duals. And the vertex set of the Delaunay complex is just X. So each Delaunay cell uniquely corresponds to a common vertex of each of the Voronoi cells of its vertices. And conversely each Voronoi cell uniquely corresponds to the common vertex of each of the Delaunay cells of its vertices.

So, having already calculated both, all the Delaunay cells, as well as their circumcenters each, you just would have to select those Delaunay cells, which are incident to x (i.e. having x for one of its vertices). Then take the set of the associated circumcenters of these cells. The hull of these circumcenters now would be the searched for Voronoi cell for that x. (I.e. that set of circumcenters is nothing but the vertex set of this Voronoi cell.)

--- rk

Answer 2

A simplex in dimension D is a strongly-connected set of N = (D+1) points, each of the N points being connected to the other (N-1) points in the simplex by a 1D line segment.

The hyperplanes of a Voronoi division are each (D-1) dimension, and are each formed/constructed as a perpendicular bisector of one of these segments. Cutting through halfway in the middle. So the (D-1) dimension of the hyperplane, plus the 1 dimension of the segment, fill up all of the D degrees of freedom of your D space.

A hyperplane has orientation (handedness), there's a top side and a bottom side. You can tell which is which with regards to its segment points by taking the signed distance from the plane to each of the points, and seeing which point is above (positive) and which is below (negative). Then you can either re-use the plane and remember which side you're on, or flip a copy of the plane and only store positive-handed planes.

Each of the corner points in your simplex network is going to be a center-seed-point for a Voronoi cell.

Then you form the list of all pairwise line-segment connections (remember the simplex is strongly connected, so it's exhaustive for each simplex), pooling the results for ALL simplices. Remembering to delete duplicates--One line segment will be re-used for many simplices around it in a fan, and you want to make sure you don't store segment BA if you already have AB.

Given a corner seed point, find the list of all Delaunay segments that use it as an endpoint. This will give you a star of all the other points that this point is connected to.

Then simply construct the perpendicular bisector hyperplanes through each of these segments, remembering to keep track of handedness, and this gives you a single Voronoi cell. Do this for each corner point, and you've got yourself your Voronoi network of seed points and bounding hyperplanes.

Remember that the points at the edge of the original Delaunay network are not completely enclosed in the Voronoi, and have no "back side" to them.

So given all this, what about the question in the last paragraph?

It is important to understand that the Delaunay network and the Voronoi network are duals of each other, so one uniquely determines the other.

It looks like you are actually working with two different Delaunay networks--a triangulation of [corner] points, and a triangulation of sphere centers.

Since each Delaunay network uniquely determines a Voronoi network, it seems like you actually have two different Voronoi networks on your hands.

In either case, if you have a cloud of points, you can classify which Voronoi cell they fall into by taking the conjunction of the sign of the distance of the point to a cell's hyperplanes. If a point's inside all of them, then you win.

You can also narrow this down by looking at the distance of a cloud of points to the enclosing sphere, and then only examining points that are inside that sphere.

An easy way to grasp this is to look at a simplest example. Stick with 2D. Start with three points forming an upright equilateral triangle, then put a fourth point in the center. The Delaunay triangulation is each point connected to all the other 3 points, which forms three triangles inside your equilateral triangle, meeting at the point in the middle. And the Voronoi cell for this center point is a downward-pointing triangle formed by bisecting each of these segments. Each of the 3 corners also contributes a non-closed V cell, for a total of 4.

Now form your circumcircles for each of the three Delaunay triangles. Each triangle consists of a base plus the center point, so the circles are going to be large, with their centers outside the big triangle, forming a mickey-mouse head. When you connect these centers, you get a SINGLE triangle for its Delaunay triangulation, pointing downwards. And the dual for this has only 3 Voronoi cells.

Hopefully a simple example will assist in making clear what you wish to accomplish. If you can do it in 2D, you should be able to extrapolate upwards. HTH