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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
R. E. Barnhill. Representation and approximation of surfaces. InMath. Software III, J. R. Rice, ed., Academic Press, New York, 1977, pp. 69–120.
M. W. Bern and D. Eppstein. Mesh generation and optimal triangulation. InComputing in Euclidean Geometry, D. Z. Du and F. K. Hwang, eds., World Scientific, Singapore, 1992, pp. 23–90.
K. Q. Brown. Voronoi diagrams from convex hulls.Inform. Process. Lett. 9 (1979), 223–228.
T. H. Cormen, C. E. Leiserson, and R. L. Rivest.Introduction to Algorithms. MIT Press, Cambridge, MA, 1990.
E. F. D'Azevedo and R. B. Simpson. On optimal interpolation triangle incidences.SIAM J. Sci. Statist. Comput. 10 (1989), 1063–1075.
B. Delaunay. Sur la sphère vide.Izv. Akad. Nauk SSSR, Otdel. Mat. Estestv. Nauk 7 (1934), 793–800.
N. Dyn, D. Levin, and S. Rippa. Data dependent triangulations for piecewise linear interpolation.IMA J. Numer. Anal. 10 (1990), 137–154.
H. Edelsbrunner.Algorithms in Combinatorial Geometry. Springer-Verlag, Heidelberg, 1987.
H. Edelsbrunner and E. P. Mücke. Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms.ACM Trans. Graphics 9 (1990), 66–104.
H. Edelsbrunner, T. S. Tan, and R. Waupotitsch. AnO(n 2 logn) time algorithm for the minmax angle triangulation.SIAM J. Statist. Sci. Comput. 13 (1992), 994–1008.
H. Edelsbrunner and R. Waupotitsch. Optimal two-dimensional triangulations. InAnimation of Geometric Algorithms: A Video Review, M. Brown and J. Hershberger, eds. (Technical Report 87a), Systems Research Center, DEC, Palo Alto, CA, 1992, pp. 7–8.
S. Fortune. A sweepline algorithm for Voronoi diagrams.Algorithmica 2 (1987), 153–174.
J. A. George. Computer implementation of the finite element method. Ph.D. Thesis, Technical Report STAN-CS-71-208, Computer Science Dept., Stanford University, 1971.
L. J. Guibas, D. E. Knuth, and M. Sharir. Randomized incremental construction of Delaunay and Voronoi diagrams.Algorithmica 7 (1992), 381–413.
L. J. Guibas and J. Stolfi. Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams.ACM Trans. Graphics 4 (1985), 74–123.
G. T. Klincsek. Minimal triangulations of polygonal domains.Ann. Discrete Math. 9 (1980), 121–123.
C. L. Lawson. Generation of a triangular grid with applications to contour plotting. Technical Memo 299, Jet Propulsion Laboratory, California Institute of Technology, Pasadana, CA, 1972.
C. L. Lawson. Software forC 1 surface interpolation. InMath. Software III, J. R. Rice, ed., Academic Press, New York, 1977, pp. 161–194.
D. A. Lindholm. Automatic triangular mesh generation on surfaces of polyhedra.IEEE Trans. Magnetics 19 (1983), 2539–2542.
E. L. Lloyd. On triangulations of a set of points in the plane. InProc. 18th Annual IEEE Symposium on the Foundations of Computer Science, 1977, pp. 228–240.
F. P. Preparata and M. I. Shamos.Computational Geometry—an Introduction. Springer-Verlag, New York, 1985.
V. T. Rajan. Optimality of the Delaunay triangulation in ℜd. InProc. 7th Annual Symposium on Computational Geometry, 1991, pp. 357–363.
S. Rippa. Minimal roughness property of the Delaunay triangulation.Comput. Aided Geom. Design 7 (1990), 489–497.
L. L. Schumaker. Triangulation methods. InTopics in Multivariate Approximation, C. K. Chui, L. L. Schumaker, and F. L. Utreras, eds., Academic Press, New York, 1987, pp. 219–232.
M. I. Shamos and D. Hoey. Closest point problems. InProc. 16th Annual IEEE Symposium on the Foundations of Computer Science, 1975, pp. 151–162.
R. Sibson. Locally equiangular triangulations.Comput. J. 21 (1978), 243–245.
G. Strang and G. Fix.An Analysis of the Finite Element Method. Prentice-Hall, Englewood Cliffs, NJ, 1973.
D. F. Watson and G. M. Philip. Systematic triangulations.Comput. Vision Graphics Image Process.26 (1984), 217–223.
Author information
Authors and Affiliations
Additional information
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.
Rights and permissions
About this article
Cite this article
Bern, M., Edelsbrunner, H., Eppstein, D. et al. Edge insertion for optimal triangulations. Discrete Comput Geom 10, 47–65 (1993). https://doi.org/10.1007/BF02573962
Received:
Revised:
Published:
Issue date:
DOI: https://doi.org/10.1007/BF02573962