Abstract
Two-dimensional constrained Delaunay triangulations are geometric structures that are popular for interpolation and mesh generation because they respect the shapes of planar domains, they have “nicely shaped” triangles that optimize several criteria, and they are easy to construct and update. The present work generalizes constrained Delaunay triangulations (CDTs) to higher dimensions and describes constrained variants of regular triangulations, here christened weighted CDTs and constrained regular triangulations. CDTs and weighted CDTs are powerful and practical models of geometric domains, especially in two and three dimensions.
The main contributions are rigorous, theory-tested definitions of CDTs and piecewise linear complexes (geometric domains that incorporate nonconvex faces with “internal” boundaries), a characterization of the combinatorial properties of CDTs and weighted CDTs (including a generalization of the Delaunay Lemma), the proof of several optimality properties of CDTs when they are used for piecewise linear interpolation, and a simple and useful condition that guarantees that a domain has a CDT. These results provide foundations for reasoning about CDTs and proving the correctness of algorithms. Later articles in this series discuss algorithms for constructing and updating CDTs.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aichholzer, O., Aurenhammer, F., Krasser, H., Brass, P.: Pseudotriangulations from surfaces and a novel type of edge flip. SIAM J. Comput. 32(6), 1621–1653 (2003)
Aurenhammer, F.: Power diagrams: properties, algorithms, and applications. SIAM J. Comput. 16(1), 78–96 (1987)
Aurenhammer, F., Krasser, H.: Pseudo-tetrahedral complexes. In: Proceedings of the Twenty-First European Workshop on Computational Geometry, Eindhoven, The Netherlands, March 2005, pp. 85–88 (2005)
Bern, M., Eppstein, D.: Mesh generation and optimal triangulation. In: Du, D.-Z., Hwang, F. (eds.) Computing in Euclidean Geometry. Lecture Notes Series on Computing, vol. 1, pp. 23–90. World Scientific, Singapore (1992)
Brown, K.Q.: Voronoi diagrams from convex hulls. Inf. Process. Lett. 9, 223–228 (1979)
Cheng, S.-W., Dey, T.K.: Quality meshing with weighted Delaunay refinement. In: Proceedings of the Thirteenth Annual Symposium on Discrete Algorithms, San Francisco, CA, January 2002, pp. 137–146. Association for Computing Machinery, New York (2002)
Cheng, S.-W., Dey, T.K., Edelsbrunner, H., Facello, M.A., Teng, S.-H.: Sliver exudation. J. ACM 47(5), 883–904 (2000)
Cheng, S.-W., Poon, S.-H.: Graded conforming Delaunay tetrahedralization with bounded radius-edge ratio. In: Proceedings of the Fourteenth Annual Symposium on Discrete Algorithms, Baltimore, MD, January 2003, pp. 295–304. Society for Industrial and Applied Mathematics, Philadelphia (2003)
Chew, L.P.: Constrained Delaunay triangulations. Algorithmica 4(1), 97–108 (1989)
Chew, L.P.: Guaranteed-quality triangular meshes. Technical Report TR-89-983, Department of Computer Science, Cornell University (1989)
Chew, L.P.: Guaranteed-quality Delaunay meshing in 3D. In: Proceedings of the Thirteenth Annual Symposium on Computational Geometry, Nice, France, June 1997, pp. 391–393. Association for Computing Machinery, New York (1997)
Cohen-Steiner, D., de Verdière, É.C., Yvinec, M.: Conforming Delaunay triangulations in 3D. In: Proceedings of the Eighteenth Annual Symposium on Computational Geometry, Barcelona, Spain, June 2002, pp. 199–208. Association for Computing Machinery, New York (2002)
D’Azevedo, E.F., Simpson, R.B.: On optimal interpolation triangle incidences. SIAM J. Sci. Stat. Comput. 10, 1063–1075 (1989)
Delaunay, B.N.: Sur la sphère vide. Izv. Akad. Nauk SSSR, VII Ser. 7, 793–800 (1934)
Edelsbrunner, H.: An acyclicity theorem for cell complexes in d dimension. Combinatorica 10(3), 251–260 (1990)
Edelsbrunner, H., Guoy, D.: An experimental study of sliver exudation. In: Tenth International Meshing Roundtable, Newport Beach, CA, October 2001, pp. 307–316. Sandia National Laboratories (2001)
Edelsbrunner, H., Mücke, E.P.: Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms. ACM Trans. Graph. 9(1), 66–104 (1990)
Edelsbrunner, H., Seidel, R.: Voronoi diagrams and arrangements. Discrete Comput. Geom. 1, 25–44 (1986)
Edelsbrunner, H., Shah, N.R.: Incremental topological flipping works for regular triangulations. Algorithmica 15(3), 223–241 (1996)
Edelsbrunner, H., Tan, T.S.: An upper bound for conforming Delaunay triangulations. Discrete Comput. Geom. 10(2), 197–213 (1993)
Fortune, S.: Voronoi diagrams and Delaunay triangulations. In: Du, D.-Z., Hwang, F. (eds.) Computing in Euclidean Geometry. Lecture Notes Series on Computing, vol. 1, pp. 193–233. World Scientific, Singapore (1992)
George, P.-L., Borouchaki, H.: Delaunay Triangulation and Meshing: Application to Finite Elements. Hermès, Paris (1998)
Gomes, A.J.P.: A concise B-rep data structure for stratified subanalytic objects. In:Kobbelt, L., Schröder, P., Hoppe, H. (eds.) Eurographics Symposium on Geometry Processing, Aachen, Germany, June 2003, pp. 83–93 (2003)
Grislain, N., Shewchuk, J.R.: The strange complexity of constrained Delaunay triangulation. In: Proceedings of the Fifteenth Canadian Conference on Computational Geometry, Halifax, Nova Scotia, August 2003, pp. 89–93 (2003)
Grünbaum, B., Shephard, G.C.: A new look at Euler’s theorem for polyhedra. Am. Math. Mon. 101(2), 109–128 (1994)
Hadwiger, H.: Vorlesungen über Inhalt, Oberfläche und Isoperimetrie. Springer, Berlin (1957)
Hazlewood, C.: Approximating constrained tetrahedrizations. Comput. Aided Geom. Des. 10, 67–87 (1993)
Lawson, C.L.: Software for C 1 surface interpolation. In: Rice, J.R. (ed.) Mathematical Software III, pp. 161–194. Academic Press, New York (1977)
Lee, D.-T., Lin, A.K.: Generalized Delaunay triangulations for planar graphs. Discrete Comput. Geom. 1, 201–217 (1986)
Li, X.-Y., Teng, S.-H.: Generating well-shaped Delaunay meshes in 3D. In: Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, Washington, DC, January 2001, pp. 28–37. Association for Computing Machinery, New York (2001)
Melissaratos, E.A.: L p optimal d dimensional triangulations for piecewise linear interpolation: a new result on data dependent triangulations. Technical Report RUU-CS-93-13, Department of Computer Science, Utrecht University, Utrecht, April 1993
Miller, G.L., Talmor, D., Teng, S.-H., Walkington, N., Wang, H.: Control volume meshes using sphere packing: generation, refinement and coarsening. In: Fifth International Meshing Roundtable, Pittsburgh, PA, October 1996, pp. 47–61 (1996)
Murphy, M., Mount, D.M., Gable, C.W.: A point-placement strategy for conforming Delaunay tetrahedralization. In: Proceedings of the Eleventh Annual Symposium on Discrete Algorithms, January 2000, pp. 67–74. Association for Computing Machinery, New York (2000)
Pav, S.E., Walkington, N.J.: Robust three dimensional Delaunay refinement. In: Thirteenth International Meshing Roundtable, Williamsburg, VA, September 2004, Sandia National Laboratories, pp. 145–156 (2004)
Powar, P.L.: Minimal roughness property of the Delaunay triangulation: a shorter approach. Comput. Aided Geom. Des. 9(6), 491–494 (1992)
Rajan, V.T.: Optimality of the Delaunay triangulation in ℝd. In: Proceedings of the Seventh Annual Symposium on Computational Geometry, North Conway, NH, June 1991, pp. 357–363 (1991)
Rippa, S.: Minimal roughness property of the Delaunay triangulation. Comput. Aided Geom. Des. 7(6), 489–497 (1990)
Rippa, S.: Long and thin triangles can be good for linear interpolation. SIAM J. Numer. Anal. 29(1), 257–270 (1992)
Ruppert, J.M.: Results on triangulation and high quality mesh generation. PhD thesis, University of California at Berkeley, Berkeley, CA (1992)
Ruppert, J., Seidel, R.: On the difficulty of triangulating three-dimensional nonconvex polyhedra. Discrete Comput. Geom. 7(3), 227–253 (1992)
Schönhardt, E.: Über die Zerlegung von Dreieckspolyedern in Tetraeder. Math. Ann. 98, 309–312 (1928)
Seidel, R.: Voronoi diagrams in higher dimensions. Diplomarbeit, Institut für Informationsverarbeitung, Technische Universität Graz (1982)
Seidel, R.: Constrained Delaunay triangulations and Voronoi diagrams with obstacles. In: Poingratz, H.S., Schinnerl, W. (eds.) 1978–1988 Ten Years IIG, pp. 178–191. Institute for Information Processing, Graz University of Technology (1988)
Shewchuk, J.R.: Delaunay refinement mesh generation. PhD thesis, School of Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania, May 1997. Available as Technical Report CMU-CS-97-137
Shewchuk, J.R.: A condition guaranteeing the existence of higher-dimensional constrained Delaunay triangulations. In: Proceedings of the Fourteenth Annual Symposium on Computational Geometry, Minneapolis, MN, June 1998, pp. 76–85. Association for Computing Machinery, New York (1998)
Shewchuk, J.R.: Mesh generation for domains with small angles. In: Proceedings of the Sixteenth Annual Symposium on Computational Geometry, Hong Kong, June 2000, pp. 1–10. Association for Computing Machinery, New York (2000)
Shewchuk, J.R.: Constrained Delaunay tetrahedralizations and provably good boundary recovery. In: Eleventh International Meshing Roundtable, Ithaca, NY, September 2002, pp. 193–204. Sandia National Laboratories (2002)
Shewchuk, J.R.: Delaunay refinement algorithms for triangular mesh generation. Comput. Geom. Theory Appl. 22(1–3), 21–74 (2002)
Si, H., Gärtner, K.: Meshing piecewise linear complexes by constrained Delaunay tetrahedralizations. In: Hanks, B.W. (ed.) Proceedings of the Fourteenth International Meshing Roundtable, San Diego, CA, September 2005, pp. 147–163 (2005)
Sibson, R.: A brief description of natural neighbor interpolation. In: Barnett, V. (ed.) Interpreting Multivariate Data, pp. 22–36. Wiley, New York (1981)
Waldron, S.: The error in linear interpolation at the vertices of a simplex. SIAM J. Numer. Anal. 35(3), 1191–1200 (1998)
Weatherill, N.P., Hassan, O.: Efficient three-dimensional grid generation using the Delaunay triangulation. In: Hirsch, Ch., Périaux, J., Kordulla, W. (eds.) Proceedings of the First European Computational Fluid Dynamics Conference, Brussels, Belgium, September 1992, pp. 961–968 (1992)
Weatherill, N.P., Hassan, O., Marcum, D.L., Marchant, M.J.: Grid Generation by the Delaunay Triangulation. Von Karman Institute for Fluid Dynamics 1993–1994 Lecture Series (1994)
Ziegler, G.M.: Lectures on Polytopes, 1st edn. Springer, New York (1995)
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported in part by the National Science Foundation under Awards CMS-9318163, ACI-9875170, CMS-9980063, CCR-0204377, CCF-0430065, and EIA-9802069, in part by the Advanced Research Projects Agency and Rome Laboratory, Air Force Materiel Command, USAF under agreement number F30602-96-1-0287, in part by an Alfred P. Sloan Research Fellowship, and in part by gifts from the Okawa Foundation and Intel. The views in this document are those of the author. They are not endorsed by the sponsors or the U.S. Government.
Rights and permissions
About this article
Cite this article
Shewchuk, J.R. General-Dimensional Constrained Delaunay and Constrained Regular Triangulations, I: Combinatorial Properties. Discrete Comput Geom 39, 580–637 (2008). https://doi.org/10.1007/s00454-008-9060-3
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-008-9060-3