Voronoi diagram of a set of vertices of a mesh.

Question

i have a triangulated mesh. I have some vertices which are part of the vertices of the mesh. Is there any algorithm to compute the voronoi diagram of these set of vertices. The triangulated mesh surface is non-planar. The resulting voronoi diagram should share the already existing edges and vertices.

Answer 1

Given a triangulated mesh, e.g. even a triangular planar graph in 2-d, if you choose a subset of vertices there is no guarantee that the vertices and edges of this Voronoi diagram for the subset of vertices will be a subset of vertices and edges of your original planar graph. And even if you could guarantee they were, there is probably no easy way to tell what the edges of the Voronoi diagram are, noticeably any faster than just computing the Voronoi diagram outright for the subset of vertices using the fastest algorithms. That's at least the case in 2 dimensions. In higher dimensions, if you assume that the triangular mesh is lower dimensional, e.g. 2-d then you might be able to do faster than computing the Voronoi diagram outright in the higher dimensional space, assuming that the faces of the diagram intersected with the mesh are all faces in your mesh, but it still seems like a highly non-trivial problem.