3
$\begingroup$

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.

$\endgroup$

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.