EDGE INSERTION FOR OPTIMAL TRIANGULATIONS

Authors
BERN M EDELSBRUNNER H EPPSTEIN D MITCHELL S TAN TS
Citation
M. Bern et al., EDGE INSERTION FOR OPTIMAL TRIANGULATIONS, Discrete & computational geometry, 10(1), 1993, pp. 47-65
Citations number
28
Categorie Soggetti
Computer Sciences, Special Topics","Mathematics, Pure","Computer Applications & Cybernetics",Mathematics
Journal title
Discrete & computational geometry → ACNP
ISSN journal
01795376
Volume
10
Issue
1
Year of publication
1993
Pages
47 - 65
Database
ISI
SICI code
0179-5376(1993)10:1<47:EIFOT>2.0.ZU;2-N
Abstract
Edge insertion iteratively improves a triangulation of a finite point set in R2 by adding a new edge, deleting old edges crossing the new ed ge, and retriangulating the polygonal regions on either side of the ne w edge. This paper presents an abstract view of the edge insertion par adigm, and then shows that it gives polynomial-time algorithms for sev eral types of optimal triangulations, including minimizing the maximum slope of a piecewise-linear interpolating surface.