Edge insertion for optimal triangulations

M. Bern, H. Edelsbrunner, D. Eppstein, S. Mitchell, T. Tan, Discrete & Computational Geometry 10 (1993) 47–65.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
; ; ; ;
Abstract
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.
Publishing Year
Date Published
1993-12-01
Journal Title
Discrete & Computational Geometry
Acknowledgement
National Science Foundation under Grant No. CCR-8921421 and under the Alan T. Waterman award, Grant No. CCR-9118874.
Volume
10
Issue
1
Page
47 - 65
IST-REx-ID

Cite this

Bern M, Edelsbrunner H, Eppstein D, Mitchell S, Tan T. Edge insertion for optimal triangulations. Discrete & Computational Geometry. 1993;10(1):47-65. doi:10.1007/BF02573962
Bern, M., Edelsbrunner, H., Eppstein, D., Mitchell, S., & Tan, T. (1993). Edge insertion for optimal triangulations. Discrete & Computational Geometry, 10(1), 47–65. https://doi.org/10.1007/BF02573962
Bern, Marshall, Herbert Edelsbrunner, David Eppstein, Stephen Mitchell, and Tiow Tan. “Edge Insertion for Optimal Triangulations.” Discrete & Computational Geometry 10, no. 1 (1993): 47–65. https://doi.org/10.1007/BF02573962.
M. Bern, H. Edelsbrunner, D. Eppstein, S. Mitchell, and T. Tan, “Edge insertion for optimal triangulations,” Discrete & Computational Geometry, vol. 10, no. 1, pp. 47–65, 1993.
Bern M, Edelsbrunner H, Eppstein D, Mitchell S, Tan T. 1993. Edge insertion for optimal triangulations. Discrete & Computational Geometry. 10(1), 47–65.
Bern, Marshall, et al. “Edge Insertion for Optimal Triangulations.” Discrete & Computational Geometry, vol. 10, no. 1, Springer, 1993, pp. 47–65, doi:10.1007/BF02573962.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar