Edge insertion for optimal triangulations


Journal Article

Edge insertion iteratively improves a triangulation of a finite point set in ℜ2 by adding a new edge, deleting old edges crossing the new edge, and retriangulating the polygonal regions on either side of the new edge. This paper presents an abstract view of the edge insertion paradigm, and then shows that it gives polynomial-time algorithms for several types of optimal triangulations, including minimizing the maximum slope of a piecewise-linear interpolating surface. © 1993 Springer-Verlag New York Inc.

Full Text

Cited Authors

  • Bern, M; Edelsbrunner, H; Eppstein, D; Mitchell, S; Tan, TS

Published Date

  • December 1, 1993

Published In

Volume / Issue

  • 10 / 1

Start / End Page

  • 47 - 65

Electronic International Standard Serial Number (EISSN)

  • 1432-0444

International Standard Serial Number (ISSN)

  • 0179-5376

Digital Object Identifier (DOI)

  • 10.1007/BF02573962

Citation Source

  • Scopus