Edge insertion for optimal triangulations
Bern M, Edelsbrunner H, Eppstein D, Mitchell S, Tan T. 1993. Edge insertion for optimal triangulations. Discrete & Computational Geometry. 10(1), 47–65.
Download
No fulltext has been uploaded. References only!
Journal Article
| Published
| English
Scopus indexed
Author
Bern, Marshall;
Edelsbrunner, HerbertISTA 
;
Eppstein, David;
Mitchell, Stephen;
Tan, Tiow
;
Eppstein, David;
Mitchell, Stephen;
Tan, TiowAbstract
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
The authors thank two anonymous referees for suggestions on improving the style of this paper. The research of the second' author was supported by the National Science Foundation under Grant No. CCR-8921421 and under the Alan T. Waterman award, Grant No. CCR-9118874. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the view of the National Science Foundation. Part of the work was done while the second, third, and fourth authors visited the Xerox Palo Alto Research Center,
and while the fifth author was on study leave at the University of Illinois.
Volume
10
Issue
1
Page
47 - 65
ISSN
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. Springer. 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. Springer, 1993. 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. Springer, 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.
Link(s) to Main File(s)
Access Level
Closed Access
Google Scholar