CGAL 5.6.3 - dD Triangulations

Loading...
Searching...
No Matches
User Manual

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).