Edge insertion for optimal triangulations - Bern, Marshall; Edelsbrunner, Herbert; Eppstein, David; Mitchell, Stephen; Tan, Tiow; Simon, Imre; LATIN: Latin American Symposium on Theoretical Informatics (1st Latin American Symposium on Theoretical Informatics, 1992)
The edge-insertion paradigm improves a triangulation of a finite point set in R2 iteratively by adding a new edge, deleting intersecting old edges, and retriangulating the resulting two polygonal regions. After presenting an abstract view of the paradigm, this paper shows that it can be used to obtain polynomial time algorithms for several types of optimal triangulations.
published
yes
yes
Keywords: conference paper