Skip to Main content Skip to Navigation

Delaunay Tessellations and Voronoi Diagrams in CGAL

Pierre Alliez 1 Christophe Delage 2 Menelaos Karavelas 3 Sylvain Pion 2 Monique Teillaud 2 Mariette Yvinec 2
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée
2 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : The Cgal library provides a rich variety of Voronoi diagrams and Delaunay triangulations. This variety covers several aspects: generators, dimensions and metrics, which we describe in Section 2. One aim of this paper is to present the main paradigms used in CGAL: Generic programming, separation between predicates/constructions and combinatorics, and exact geometric computation (not to be confused with exact arithmetic!). The first two paradigms translate into software design choices, described in Section 4, while the last covers both robustness and efficiency issues, respectively described in Sec- tion 6 and 7. Other important aspects of the Cgal library are the interface issues, be they for traversing a tessellation, or for interoperability with other libraries or languages, see Section 5. We present in Section 8 some tessellations at work in the context of surface reconstruction and mesh generation. Section 9 is devoted to some on-going and future work on periodic triangulations (triangulations in periodic spaces), and on high-quality mesh generation with optimized tessellations. Section 10 provides typical numbers in terms of efficiency and scalability for constructing tessellations, and lists the remaining weaknesses. We conclude by listing some of our directions for the future.
Document type :
Complete list of metadatas
Contributor : Monique Teillaud <>
Submitted on : Wednesday, December 21, 2016 - 2:08:05 PM
Last modification on : Wednesday, October 30, 2019 - 7:36:17 PM
Document(s) archivé(s) le : Tuesday, March 21, 2017 - 1:05:42 PM


Files produced by the author(s)


  • HAL Id : hal-01421021, version 1



Pierre Alliez, Christophe Delage, Menelaos Karavelas, Sylvain Pion, Monique Teillaud, et al.. Delaunay Tessellations and Voronoi Diagrams in CGAL. [Research Report] INRIA Sophia Antipolis - Méditerranée; University of Crete. 2010. ⟨hal-01421021⟩



Record views


Files downloads