Computing Delaunay Triangulations for Comet-Shaped Polygons

摘要

The author presents two triangulation algorithms which combined produce an algorithm for computing Delaunay triangulations for comet-shaped polygons. The first algorithm constructs in linear time a triangulation for a comet-shaped polygon. The second algorithm constructs a Delaunay triangulation for a polygon from any triangulation for the polygon. The algorithms can be used for deleting vertices in a Delaunay triangulation and for computing constrained Delaunay triangulations.