Fast Voronoi Diagrams and Offsets on Triangulated Surfaces
Ron Kimmel, James A. Sethian · 2000
We apply the Fast Marching Method on triangulated domains to efficiently compute Voronoi diagrams and offset curves on triangulated manifolds. The computational complexity of the proposed algorithm is optimal, O(M log M), where M is the number of vertices. The algorithm also applies to weighted domains in which a different cost is assigned to each surface point.