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:
- The vertices of the polytope
- The faces of the polytope and their vertices
- The location of a central point
- The radial lines passing through the faces
- The fact that the polytope forms a convex hull
The main issues are:
- 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.