Authors: Olivier Devillers, Samuel Hornus, and Clément Jamin.

This package proposes data structures and algorithms to compute triangulations of points in any dimensions [1]. The Triangulation_data_structure handles the combinatorial aspect of triangulations while the geometric classes Triangulation, Delaunay_triangulation and Regular_triangulation allow to compute and maintain triangulations, Delaunay triangulations, and regular triangulations of sets of points.

Introduction

Some Definitions

A finite abstract simplicial complex is built on a finite set of vertices \( V\) and consists of a collection \( S\) of subsets of \( V\) such that, if \( s\) is a set of vertices in \( S\), then all the subsets of \( s\) are also in \( S\).

The sets in \( S\) (which are subsets of \( V\)) are called faces or simplices (the singular of which is simplex). A simplex \( s\in S\) is maximal if it is not a proper subset of some other set in \( S\). A simplex having \( k+1 \) vertices is said of dimension \( k \). An \( k\)-face denotes a \( k\)-dimensional simplex, i.e., a simplex with \( k+1\) vertices. The simplicial complex is pure if all the maximal simplices have the same dimension.

A triangulation is a simplicial complex that is pure, connected and without boundaries nor singularities. The dimension of the triangulation is the dimension of its maximal simplices.

[1] for more details.

We provide below (Figure 48.1, Figure 48.2 and Figure 48.3) the performance of the Delaunay triangulation on randomly distributed points. The machine used is a PC running Windows 7 64-bits with an Intel Xeon CPU clocked at 2.80 GHz with 32GB of RAM. The program has been compiled with Microsoft Visual C++ 2013 in Release mode.

Dimension	2	3	4	5	6	7	8	9	10	11	12


Time (s)	0.003	0.007	0.03	0.14	0.56	2.7	11.3	45	185	686	2390
Memory (MB)	< 1	< 1	< 1	1	3	13	53	182	662	2187	7156
Number of maximal simplices	184	487	1,548	5,548	19,598	67,102	230,375	715,984	2,570,623	7,293,293	21,235,615
Number of convex hull facets	14	66	308	1,164	4,410	16,974	57,589	238,406	670,545	2,574,326	8,603,589

Figure 48.1 Performance of the insertion of 100 points in a Delaunay triangulation.

Dimension	2	3	4	5	6	7	8


Time (s)	0.01	0.05	0.5	3.4	24	183	1365
Memory (MB)	< 1	< 1	2.7	14	81	483	2827
Number of maximal simplices	1,979	6,315	25,845	122,116	596,927	3,133,318	16,403,337
Number of convex hull facets	19	138	963	6,184	41,135	241,540	1,406,797

Figure 48.2 Performance of the insertion of 1000 points in a Delaunay triangulation.

Figure 48.3 Running time wrt. number of maximal simplices, for dimensions for 2 to 12.

Design and Implementation History

Starting with the version 2.3 of CGAL, a package written by Susan Hert and Michael Seel was the first able to deal with triangulation and convex hulls in arbitrary dimension. It is deprecated since the version 4.6 of CGAL and this package should be used instead.

This package is heavily inspired by the works of Monique Teillaud and Sylvain Pion (Triangulation_3) and Mariette Yvinec (Triangulation_2). The first version was written by Samuel Hornus. The final version is a joint work by Samuel Hornus, Olivier Devillers and Clément Jamin. In 2017, Clément Jamin added the regular triangulations.

Clément Jamin's work was supported by the Advanced Grant of the European Research Council GUDHI (Geometric Understanding in Higher Dimensions).