zbMATH — the first resource for mathematics

Triangulations in CGAL. (English) Zbl 1016.68138
Summary: This paper presents the main algorithmic and design choices that have been made to implement triangulations in the Computational Geometry Algorithms Library (CGAL).

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDF BibTeX Cite
Full Text: DOI
[1] Aurenhammer, F., Voronoi diagrams: A survey of a fundamental geometric data structure, ACM comput. surv., 23, 3, 345-405, (1991)
[2] B. Barber, Qhull, http://www.geom.umn.edu/locate/qhull, Version 2.3
[3] Barber, C.B.; Dobkin, D.P.; Huhdanpaa, H., The quickhull algorithm for convex hulls, ACM trans. math. softw., 22, 4, 469-483, (1996) · Zbl 0884.65145
[4] Bern, M.; Eppstein, D., Mesh generation and optimal triangulation, (), 23-90
[5] Bertrand, Y.; Dufourd, J.-F., Algebraic specification of a 3D-modeler based on hypermaps, CVGIP: graph. models image process., 56, 29-60, (1994)
[6] Boissonnat, J.-D.; Yvinec, M., Algorithmic geometry, (1998), Cambridge University Press UK, Translated by Hervé Brönnimann
[7] Brisson, E., Representing geometric structures in d dimensions: topology and order, Discrete comput. geom., 9, 387-426, (1993) · Zbl 0783.68129
[8] Brönnimann, H.; Burnikel, C.; Pion, S., Interval arithmetic yields efficient dynamic filters for computational geometry, (), 165-174
[9] Cazier, D.; Dufourd, J.-F., A formal specification of geometric refinements, Visual computer, 15, 279-301, (1999)
[10] de Berg, M.; van Kreveld, M.; Overmars, M.; Schwarzkopf, O., Computational geometry: algorithms and applications, (1997), Springer-Verlag Berlin
[11] de Berg, M.; van Oostrum, R.; Overmars, M., Simple traversal of a subdivision without extra storage, (), C5-C6
[12] O. Devillers, The Delaunay hierarchy, http://www-sop.inria.fr/prisme/logiciel/del-hierarchy/ · Zbl 1066.68138
[13] Devillers, O., Improved incremental randomized Delaunay triangulation, (), 106-115
[14] Devillers, O.; Liotta, G.; Preparata, F.P.; Tamassia, R., Checking the convexity of polytopes and the planarity of subdivisions, Comput. geom. theory appl., 11, 187-208, (1998) · Zbl 0921.68101
[15] Devillers, O.; Pion, S.; Teillaud, M., Walking in a triangulation, () · Zbl 1374.68659
[16] Devillers, O.; Pion, S.; Teillaud, M., Walking in a triangulation, rapport de recherche 4120, (2001), INRIA · Zbl 1374.68659
[17] Dwyer, R.A., A simple divide-and-conquer algorithm for computing Delaunay triangulations in O(nloglogn) expected time, (), 276-284
[18] Dwyer, R.A., A faster divide-and-conquer algorithm for constructing Delaunay triangulations, Algorithmica, 2, 137-151, (1987) · Zbl 0631.68043
[19] Edelsbrunner, H.; Seidel, R., Voronoi diagrams and arrangements, Discrete comput. geom., 1, 25-44, (1986) · Zbl 0598.52013
[20] Edelsbrunner, H.; Tan, T.S., An upper bound for conforming Delaunay triangulations, Discrete comput. geom., 10, 2, 197-213, (1993) · Zbl 0774.68093
[21] Fabri, A.; Giezeman, G.-J.; Kettner, L.; Schirra, S.; Schönherr, S., On the design of CGAL, the computational geometry algorithms library, research report 3407, (1998), INRIA
[22] Flato, E.; Halperin, D.; Hanniel, I.; Nechushtan, O., The design and implementation of planar maps in CGAL, (), 169-172
[23] Flekkøy, E.G.; Coveney, P.V.; De Fabritis, G., Foundations of dissipative particle dynamics, Phys. rev. E, 62, 2140, (2000)
[24] George, P.-L.; Borouchaki, H., Triangulation de Delaunay et maillage. applications aux éléments finis, (1997), Hermes Paris, France
[25] Granlund, T., GMP, the GNU multiple precision arithmetic library, (1996), http://www.swox.com/gmp/
[26] Guibas, L.J.; Stolfi, J., Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams, ACM trans. graph., 4, 2, 74-123, (1985) · Zbl 0586.68059
[27] Hoffmann, F.; Kriegel, K.; Wenk, C., A geometric approach to protein identification in 2D electrophoretic gel images, (), 173-174
[28] Kettner, L., Using generic programming for designing a data structure for polyhedral surfaces, Comput. geom. theory and appl., 13, 65-90, (1999) · Zbl 0935.68122
[29] LEDA, http://www.mpi-sb.mpg.de/LEDA/, Version 4.0
[30] Lienhardt, P., N-dimensional generalized combinatorial maps and cellular quasi-manifolds, Internat. J. comput. geom. appl., 4, 3, 275-324, (1994) · Zbl 0821.57016
[31] D. Lischinski, Graphics Gems IV, ftp://wuarchive.wustl.edu/graphics/graphics/books/graphics-gems/
[32] Mücke, E.P.; Saias, I.; Zhu, B., Fast randomized point location without preprocessing in two- and three-dimensional Delaunay triangulations, (), 274-283
[33] Mulmuley, K., Randomized multidimensional search trees: dynamic sampling, (), 121-131
[34] Murphy, M.; Mount, D.M.; Gable, C.W., A point-placement strategy for conforming Delaunay tetrahedralization, (), 67-74 · Zbl 0953.65010
[35] Pion, S., De la géométrie algorithmique au calcul géométrique, thèse de doctorat en sciences, (1999), Université de Nice-Sophia Antipolis France
[36] Pion, S., Interval arithmetic: an efficient implementation and an application to computational geometry, (), 99-110
[37] Schönhardt, E., Über die zerlegung von dreieckspolyedern in tetraeder, Mathematische annalen, 98, 309-312, (1928) · JFM 53.0576.01
[38] Shewchuk, J.R., Triangle: engineering a 2D quality mesh generator and Delaunay triangulator, (), 203-222
[39] J.R. Shewchuk, Triangle. A two-dimensional quality mesh generator and Delaunay triangulator, http://www.cs.cmu.edu/ quake/triangle.html, Version 1.3
[40] Shewchuk, J.R., Robust adaptive floating-point geometric predicates, (), 141-150
[41] Shewchuk, J.R., A condition guaranteeing the existence of higher-dimensional constrained Delaunay triangulations, (), 76-85
[42] Veltkamp, R.C., Generic programming in CGAL, the computational geometry algorithms library, (), 127-138
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.