@inproceedings{4049, abstract = {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.}, author = {Bern, Marshall and Edelsbrunner, Herbert and Eppstein, David and Mitchell, Stephen and Tan, Tiow}, booktitle = {1st Latin American Symposium on Theoretical Informatics}, editor = {Simon, Imre}, isbn = {978-3-540-55284-0}, location = {São Paulo, Brazil}, pages = {46 -- 60}, publisher = {Springer}, title = {{Edge insertion for optimal triangulations}}, doi = {10.1007/BFb0023816}, volume = {583}, year = {1992}, }