Edge insertion for optimal triangulations
Bern M, Edelsbrunner H, Eppstein D, Mitchell S, Tan T. 1992. Edge insertion for optimal triangulations. 1st Latin American Symposium on Theoretical Informatics. LATIN: Latin American Symposium on Theoretical Informatics , LNCS, vol. 583, 46–60.
Download
No fulltext has been uploaded. References only!
Conference Paper
| Published
| English
Scopus indexed
Author
Bern, Marshall;
Edelsbrunner, HerbertISTA 
;
Eppstein, David;
Mitchell, Stephen;
Tan, Tiow
;
Eppstein, David;
Mitchell, Stephen;
Tan, TiowEditor
Simon, Imre
Series Title
LNCS
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.
Publishing Year
Date Published
1992-04-07
Proceedings Title
1st Latin American Symposium on Theoretical Informatics
Publisher
Springer
Acknowledgement
Research of the second author is supported by the National Science Foundation under grant no. CCR-8921421 and under the Alan T. Waterman award, grant no. CCR-9118874. Any opinions, finding 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. The fifth author is on study leave from the National University of Singapore, Republic of Singapore.
Volume
583
Page
46 - 60
Conference
LATIN: Latin American Symposium on Theoretical Informatics
Conference Location
São Paulo, Brazil
Conference Date
1992-04-06 – 1992-04-10
ISBN
IST-REx-ID
Cite this
Bern M, Edelsbrunner H, Eppstein D, Mitchell S, Tan T. Edge insertion for optimal triangulations. In: Simon I, ed. 1st Latin American Symposium on Theoretical Informatics. Vol 583. Springer; 1992:46-60. doi:10.1007/BFb0023816
Bern, M., Edelsbrunner, H., Eppstein, D., Mitchell, S., & Tan, T. (1992). Edge insertion for optimal triangulations. In I. Simon (Ed.), 1st Latin American Symposium on Theoretical Informatics (Vol. 583, pp. 46–60). São Paulo, Brazil: Springer. https://doi.org/10.1007/BFb0023816
Bern, Marshall, Herbert Edelsbrunner, David Eppstein, Stephen Mitchell, and Tiow Tan. “Edge Insertion for Optimal Triangulations.” In 1st Latin American Symposium on Theoretical Informatics, edited by Imre Simon, 583:46–60. Springer, 1992. https://doi.org/10.1007/BFb0023816.
M. Bern, H. Edelsbrunner, D. Eppstein, S. Mitchell, and T. Tan, “Edge insertion for optimal triangulations,” in 1st Latin American Symposium on Theoretical Informatics, São Paulo, Brazil, 1992, vol. 583, pp. 46–60.
Bern M, Edelsbrunner H, Eppstein D, Mitchell S, Tan T. 1992. Edge insertion for optimal triangulations. 1st Latin American Symposium on Theoretical Informatics. LATIN: Latin American Symposium on Theoretical Informatics , LNCS, vol. 583, 46–60.
Bern, Marshall, et al. “Edge Insertion for Optimal Triangulations.” 1st Latin American Symposium on Theoretical Informatics, edited by Imre Simon, vol. 583, Springer, 1992, pp. 46–60, doi:10.1007/BFb0023816.
Link(s) to Main File(s)
Access Level
Closed Access
Google Scholar
ISBN Search