I'm in the process of constructing an algorithm which computes the Voronoi diagram of a set of points, but I now need a method to decompose each Voronoi cell into simplices. The information we have is:

  1. The vertices of the polytope
  2. The faces of the polytope and their vertices
  3. The location of a central point
  4. The radial lines passing through the faces
  5. The fact that the polytope forms a convex hull

The main issues are:

  1. The faces of the polytope can be non-simplicial

We want the total algorithm to scale well with increasing dimension, but each Voronoi polytope has an average number of vertices which increases with dimension. Unfortunately, I can't find useful information on exactly how.

EDIT: While I have no formula for the increase in the number of polytope vertices with dimension, testing shows it to be $\mathcal O(5^d)$.

If all faces were simplicial I'd draw simplices from the central point to each face. I can triangulate the non-simplicial faces and apply the above algorithm, but I still have the same question, just in a lower dimension, as each face has the above properties, except that we lack knowledge of its faces.

I'm using the Delaunay triangulation via the Bowyer-Watson algorithm at the moment, as this was the method I used for computing the Voronoi diagram. There are clearly much faster approaches, but before I spend too long implementing one of them, I felt it wise to check whether there's a well-known method which I'm missing.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.