# Fast Algorithms for the Simplicial Decomposition of a Convex Polytope in N-Dimensions

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.