Edge insertion for optimal triangulations Conference Paper


Author(s): Bern, Marshall; Edelsbrunner, Herbert; Eppstein, David; Mitchell, Stephen; Tan, Tiow Seng
Title: Edge insertion for optimal triangulations
Title Series: LNCS
Affiliation
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.
Conference Title: LATIN: Latin American Symposium on Theoretical Informatics
Volume: 583
Conference Dates: April 6–10, 1992
Conference Location: São Paulo, Brazil
ISBN: 3-540-55284-7
Publisher: Springer  
Date Published: 1992-04-07
Start Page: 46
End Page: 60
Sponsor: National Science Foundation under grant no. CCR-8921421 and under the Alan T. Waterman award, grant no. CCR-9118874.
DOI: 10.1007/BFb0023816
Open access: no
IST Austria Authors
Related IST Austria Work