# Triangulations, CGAL, and hyperbolic surfaces

Monique Teillaud

► To cite this version:

Monique Teillaud. Triangulations, CGAL, and hyperbolic surfaces. Renormalization, computation and visualization in Geometry, Number Theory and Dynamics, Sep 2023, Marseille (CIRM, Centre International de Rencontres Mathématiques), France. hal-04241550

HAL Id: hal-04241550

https://inria.hal.science/hal-04241550v1

Submitted on 5 Jul 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Triangulations,
CGAL,
and
hyperbolic surfaces

<figure><img src="image_2.png" /></figure>

<figure><img src="image_3.png" /></figure>

Monique Teillaud
Thanks to the organizers!
Thanks to the organizers!

I'm leaving on Wednesday afternoon 😞

<figure><img src="image_4.png" /></figure>
Introduction
Delaunay triangulation in $\mathbb{R}^d$

<figure><img src="image_5.png" /></figure>

set of points $\mathcal{P}$
<figure><img src="image_6.png" /></figure>

set of points $\mathcal{P}$

triangulation of $CH(\mathcal{P})$
s.t.

circumscribed balls
are empty
Delaunay triangulation in $\mathbb{R}^d$

<figure><img src="image_7.png" /></figure>

set of points $\mathcal{P}$

dual
Voronoi diagram
Delaunay triangulation in $R^d$

Many applications

<figure><img src="image_8.png" /></figure>
# The Computational Geometry Algorithms Library

Open source project

LGPLv3+ / Commercial
The Computational Geometry Algorithms Library

Open source project

LGPLv3+ / Commercial

C++

Genericity/flexibility through templates

Robustness through Exact Geometric Computation [Yap]

Exact predicates $\rightsquigarrow$ exact decisions
> 100 chapters in the manual

<figure><img src="image_9.png" /><figcaption>Bounding Volumes</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Polyhedral Surface</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>BooleanOperations</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>Triangulations</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>Voronoi Diagrams</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>Mesh Generation</figcaption></figure>

<figure><img src="image_15.png" /><figcaption>Subdivision</figcaption></figure>

<figure><img src="image_16.png" /><figcaption>Simplification</figcaption></figure>

<figure><img src="image_17.png" /><figcaption>Parameterization</figcaption></figure>

<figure><img src="image_18.png" /><figcaption>Streamlines</figcaption></figure>

<figure><img src="image_19.png" /><figcaption>Ridge Detection</figcaption></figure>

<figure><img src="image_20.png" /><figcaption>Neighbour Search</figcaption></figure>

<figure><img src="image_21.png" /><figcaption>Kinetic Data structures</figcaption></figure>

<figure><img src="image_22.png" /><figcaption>Lower Envelope</figcaption></figure>

<figure><img src="image_23.png" /><figcaption>Arrangement</figcaption></figure>

<figure><img src="image_24.png" /><figcaption>Intersection Detection</figcaption></figure>

<figure><img src="image_25.png" /><figcaption>Minkowski Sum</figcaption></figure>

<figure><img src="image_26.png" /><figcaption>PCA</figcaption></figure>

<figure><img src="image_27.png" /><figcaption>Polytope distance</figcaption></figure>

<figure><img src="image_28.png" /><figcaption>QP Solver</figcaption></figure>
> 100 chapters in the manual

<figure><img src="image_29.png" /></figure>

<figure><img src="image_30.png" /></figure>

<figure><img src="image_31.png" /><figcaption>Bounding Volumes</figcaption></figure>

<figure><img src="image_32.png" /></figure>

<figure><img src="image_33.png" /><figcaption>Polyhedral Surface</figcaption></figure>

<figure><img src="image_34.png" /></figure>

<figure><img src="image_35.png" /></figure>

<figure><img src="image_36.png" /><figcaption>BooleanOperations</figcaption></figure>

<figure><img src="image_37.png" /></figure>

<figure><img src="image_38.png" /><figcaption>Triangulations</figcaption></figure>

<figure><img src="image_39.png" /></figure>

<figure><img src="image_40.png" /><figcaption>Voronoi Diagrams</figcaption></figure>

<figure><img src="image_41.png" /></figure>

<figure><img src="image_42.png" /><figcaption>Mesh Generation</figcaption></figure>

<figure><img src="image_43.png" /></figure>

<figure><img src="image_44.png" /></figure>

<figure><img src="image_45.png" /><figcaption>Subdivision</figcaption></figure>

<figure><img src="image_46.png" /><figcaption>Simplification</figcaption></figure>

<figure><img src="image_47.png" /><figcaption>Parameterization</figcaption></figure>

<figure><img src="image_48.png" /><figcaption>Streamlines</figcaption></figure>

<figure><img src="image_49.png" /><figcaption>Ridge Detection</figcaption></figure>

<figure><img src="image_50.png" /><figcaption>Neighbour Search</figcaption></figure>

<figure><img src="image_51.png" /><figcaption>Kinetic Data structures</figcaption></figure>

<figure><img src="image_52.png" /><figcaption>Lower Envelope</figcaption></figure>

<figure><img src="image_53.png" /><figcaption>Arrangement</figcaption></figure>

<figure><img src="image_54.png" /><figcaption>Intersection Detection</figcaption></figure>

<figure><img src="image_55.png" /><figcaption>Minkowski Sum</figcaption></figure>

<figure><img src="image_56.png" /><figcaption>PCA</figcaption></figure>

<figure><img src="image_57.png" /><figcaption>Polytope distance</figcaption></figure>

<figure><img src="image_58.png" /><figcaption>QP Solver</figcaption></figure>
2D Triangulations (1997)

3D Triangulations (2000) and meshes (2009)

dD Triangulations (2015)

2D Periodic Triangulations (2013)
Flat torus
square/cubic domain
(general in progress)

3D Periodic Triangulations (2009) and meshes (2018)

2D Hyperbolic Triangulations (2019)

Bolza surface

2D Periodic Hyperbolic Triangulations (2019)

Triangulations on the 2D sphere (2021)
install CGAL dependencies + Qt (example MacOS)

brew install cgal

brew install qt5

download CGAL sources with examples and demos:

https://github.com/CGAL/cgal/releases/CGAL-5.6.zip

set up environment variables

CGAL_DIR=/Users/teillaud/CGAL-5.6

Qt5_DIR=/opt/homebrew/Cellarqt@5/5.15.10_1/lib/cmake

compile demos

cd CGAL_DIR/demo/Your_favorite_package

mkdir build; cd build

cmake ..

make

run the demo(s)
$$ \text{Triangulation}_d < \text{Geom\_traits}, \text{TDS} > \\ d = 2, 3 $$
<figure><img src="image_59.png" /></figure>

* objects (points, etc)

* predicates (e.g., in_circle)

* constructions (e.g., circumcenter)
<figure><img src="image_60.png" /></figure>
[Incremental] Algorithms
Bowyer's fill-hole algorithm

$\mathbb{R}^d$

[ Bowyer 1981 ] [ Watson 1981 ]
<figure><img src="image_61.png" /><figcaption>[ Bowyer 1981 ] [ Watson 1981 ]</figcaption></figure>
[ Bowyer 1981 ] [ Watson 1981 ]

find simplices in conflict

<figure><img src="image_62.png" /></figure>
[ Bowyer 1981 ] [ Watson 1981 ]

find simplices in conflict

<figure><img src="image_63.png" /></figure>

the conflict region forms a topological ball
[ Bowyer 1981 ] [ Watson 1981 ]

<figure><img src="image_64.png" /></figure>

create new simplices
CGAL

<figure><img src="image_65.png" /></figure>

Triangulation < Geom, TDS >

find simplices in conflict
Triangulation
using Geom

create new simplices
TDS

allows for

- clean

- efficient

implementation

[T. CGAL'00] [Pion, T. CGAL'01*]
Lawson's flip algorithm

$R^d$

[ Lawson 1977 ]

[ Joe 1989 ] [ Rajan 1991 ] [ Edelsbrunner Shah 1996 ]
[ Lawson 1977 ]

[ Joe 1989 ] [ Rajan 1991 ] [ Edelsbrunner Shah 1996 ]

<figure><img src="image_66.png" /></figure>
[ Lawson 1977 ]

[ Joe 1989 ] [ Rajan 1991 ] [ Edelsbrunner Shah 1996 ]

<figure><img src="image_67.png" /></figure>

split the triangle
containing the new point
<figure><img src="image_68.png" /></figure>

check each edge
of a new triangle

[ Lawson 1977 ]

[ Joe 1989 ] [ Rajan 1991 ] [ Edelsbrunner Shah 1996 ]
[ Lawson 1977 ]

[ Joe 1989 ] [ Rajan 1991 ] [ Edelsbrunner Shah 1996 ]

flip edge if non-Delaunay

<figure><img src="image_69.png" /></figure>
[ Lawson 1977 ]

[ Joe 1989 ] [ Rajan 1991 ] [ Edelsbrunner Shah 1996 ]

<figure><img src="image_70.png" /></figure>
[ Lawson 1977 ]

[ Joe 1989 ] [ Rajan 1991 ] [ Edelsbrunner Shah 1996 ]

<figure><img src="image_71.png" /></figure>
[ Lawson 1977 ]

[ Joe 1989 ] [ Rajan 1991 ] [ Edelsbrunner Shah 1996 ]

<figure><img src="image_72.png" /></figure>

check OK
[ Lawson 1977 ]

[ Joe 1989 ] [ Rajan 1991 ] [ Edelsbrunner Shah 1996 ]

<figure><img src="image_73.png" /></figure>

propagate flips
<figure><img src="image_74.png" /></figure>

at each step

Triangulation using `Geomsts` and TDS

hard to maintain

early version of
**CGAL** in $\mathbb{R}^2$
[Yvinec CGAL'97]
Implementation “details”
<figure><img src="image_75.png" /></figure>
# Implementation “details”

## Robustness

### Predicates

<figure><img src="image_76.png" /></figure>

$$ \text{orient}(p, q, r) = \text{sign} \begin{vmatrix} 1 & 1 & 1 \\ p_x & q_x & r_x \\ p_y & q_y & r_y \end{vmatrix} $$

<figure><img src="image_77.png" /></figure>

$$ \text{in_disk}(p, q, r, s) = \text{sign} \begin{vmatrix} 1 & x_p & y_p & x_p^2 + y_p^2 \\ 1 & x_q & y_q & x_q^2 + y_q^2 \\ 1 & x_r & y_r & x_r^2 + y_r^2 \\ 1 & x_s & y_s & x_s^2 + y_s^2 \end{vmatrix} $$

center and radius are not computed

sign of polynomial expression

rational input points
Implementation “details”

Robustness

Arithmetic issues

Exact Geometric Computation paradigm [Yap]

exact predicates ≠ exact arithmetics

Filtering

easy cases are more frequent
⇒ cost ≃ cost of approximate (double) computation
Implementation “details”

Robustness

Arithmetic issues

Approximate evaluation $P^a(x)$
+ Error $\epsilon$

Filtering

$P^a(x) > \epsilon$

Yes

No

$\text{Sign}(P(x)) = \text{Sign}(P^a(x))$

Exact computation
Implementation “details”

Robustness

Degenerate cases

symbolic perturbation

only perturbs the in_sphere predicate

[Devillers, T. SODA’03, CGTA’11]
Algorithmic tricks to improve efficiency
Delaunay triangulation
in $\mathbb{H}^2$
<figure><img src="image_78.png" /></figure>

hyperbolic circles are Euclidean circles
$\mapsto$ same combinatorics as Euclidean Delaunay triangulation
<figure><img src="image_79.png" /></figure>

[Bogdanov, Devillers, T. JoCG'14]

except that some Euclidean circles
are not compact

hyperbolic circles are Euclidean circles

→ same combinatorics as Euclidean Delaunay triangulation
Hyperbolic_Delaunay_triangulation_2

inherits from

Delaunay_triangulation_2

[Bogdanov, Iordanov, T. CGAL’19]

<figure><img src="image_80.png" /></figure>
Surfaces
Closed oriented surfaces
# Closed oriented surfaces

## genus 1

$$ \mathbb{T}_u^2 \sim \mathbb{R}^2 / (\mathbb{Z}e_1 + \mathbb{Z}u) \quad \text{flat torus} $$

$$ e_1 = (1,0), u = (u_x, u_y) $$
# Closed oriented surfaces

## genus 1

$$ \mathbb{T}_u^2 \sim \mathbb{R}^2 / (\mathbb{Z}e_1 + \mathbb{Z}u) \quad \text{flat torus} $$

$$ e_1 = (1,0), u = (u_x, u_y) $$

## genus $\ge 2$

$$ S \sim \mathbb{H}^2 / G $$

* $G$ Fuchsian group

* = discrete group of
  * orientation preserving isometries of $\mathbb{H}^2$

* isometric to fundamental group $\pi_1(S)$
# Closed oriented surfaces

## genus 1

$\mathbb{T}_u^2 \sim \mathbb{R}^2/(\mathbb{Z}e_1 + \mathbb{Z}u)$ flat torus

$e_1 = (1,0), u = (u_x, u_y)$

## genus $\ge 2$

<figure><img src="image_81.png" /></figure>

Poincaré disk
model

$G$ Fuchsian group

= discrete group of
orientation preserving isometries of $\mathbb{H}^2$
isometric to fundamental group $\pi_1(S)$
# Closed oriented surfaces

genus 1

<figure><img src="image_82.png" /></figure>

universal cover

$\mathbb{T}_u^2 \sim \mathbb{R}^2/(\mathbb{Z}e_1 + \mathbb{Z}u)$ flat torus

$e_1 = (1,0), u = (u_x, u_y)$

genus $\ge 2$

<figure><img src="image_83.png" /></figure>

universal cover

$S \sim \mathbb{H}^2/G$ non-Abelian

<figure><img src="image_84.png" /></figure>

$G$ Fuchsian group

Poincaré disk
model

= discrete group of
orientation preserving isometries of $\mathbb{H}^2$
isometric to fundamental group $\pi_1(S)$
# Closed oriented surfaces

genus 1

<figure><img src="image_85.png" /></figure>

universal cover

$\pi : \mathbb{R}^2 \to \mathcal{T}^2$

$\mathcal{T}_u^2 \sim \mathbb{R}^2/(\mathbb{Z}e_1 + \mathbb{Z}u)$ flat torus

$e_1 = (1,0), u = (u_x, u_y)$

genus $\ge 2$

<figure><img src="image_86.png" /></figure>

universal cover

$\pi : \mathbb{H}^2 \to S$

$S \sim \mathbb{H}^2/G$ non-Abelian

<figure><img src="image_87.png" /></figure>

$G$ Fuchsian group

Poincaré disk
model

= discrete group of
orientation preserving isometries of $\mathbb{H}^2$
isometric to fundamental group $\pi_1(S)$
# Delaunay triangulation

flat torus

<figure><img src="image_88.png" /></figure>

universal covering space
# Delaunay triangulation

## (square) flat torus

<figure><img src="image_89.png" /></figure>
# Delaunay triangulation

## (square) flat torus

<figure><img src="image_90.png" /></figure>
# Delaunay triangulation

(cubic) 3D flat torus

Astrophysics

<figure><img src="image_91.png" /></figure>

[v.d. Weijgaert⁺]

[SoCG'12 video]

<figure><img src="image_92.png" /></figure>

[Sousbie⁺]

Particle physics
Nanostructures
etc

Granular materials

<figure><img src="image_93.png" /></figure>

[Melnikov⁺]
# Delaunay triangulation

<figure><img src="image_94.png" /><figcaption>## (Bolza) hyperbolic surface</figcaption></figure>
# Delaunay triangulation

<figure><img src="image_95.png" /><figcaption>(Bolza) hyperbolic surface</figcaption></figure>

octagon = Dirichlet domain
cell of O in Vor(GO)
<figure><img src="image_96.png" /><figcaption>## (Bolza) hyperbolic surface</figcaption></figure>
## (Bolza) hyperbolic surface

<figure><img src="image_97.png" /></figure>
<figure><img src="image_98.png" /><figcaption>## (Bolza) hyperbolic surface</figcaption></figure>
## (Bolza) hyperbolic surface

<figure><img src="image_99.png" /></figure>
Bowyer's algorithm on a surface
<figure><img src="image_100.png" /></figure>

fill the hole

the hole is a topological disk
<figure><img src="image_101.png" /></figure>

the hole is **not always** a topological disk

multiple geodesics between two points
If

$$sys(S) > 2\Delta(Q)$$

then

the hole is
a topological disk

when inserting points in any set $P \supseteq Q$
do not contain any point in $\pi^{-1}(Q)$

<figure><img src="image_102.png" /></figure>

If

diameter of the largest empty disks
in the universal cover

<figure><img src="image_103.png" /></figure>

$$\mathrm{sys}(S) > 2\Delta(Q)$$

<figure><img src="image_104.png" /></figure>

then

systole = length of a shortest
non-contractible curve on S

the hole is
a topological disk

when inserting points in any set $P \supseteq Q$
$\mathit{sys}(S) > 2\Delta(Q)$

Proof

<figure><img src="image_105.png" /></figure>
$\mathit{sys}(S) > 2\Delta(Q)$

Proof

<figure><img src="image_106.png" /></figure>

Delaunay disks = empty
$\mathrm{sys}(S) > 2\Delta(Q)$

Proof

<figure><img src="image_107.png" /></figure>

two Delaunay edges

cannot form a cycle

also in $DT(P)$ for $P \supseteq Q$

$DT(P)$ is a simplicial complex
$$sys(S) > 2\Delta(Q)$$

Proof

<figure><img src="image_108.png" /></figure>

two Delaunay edges

cannot form a cycle

also in $DT(P)$ for $P \supseteq Q$

$DT(P)$ is a simplicial complex

the hole is

a topological disk

<figure><img src="image_109.png" /></figure>
Initialize the Delaunay triangulation in $\mathbb{H}^2$ with $Q$ s.t.

$$ sys(S) > 2\Delta(Q) $$

Compute the DT directly on the surface

Insert input points

Remove the points of $Q$ if possible
Initialize the Delaunay triangulation in $\mathbb{H}^2$ with $Q$ s.t.

$$ sys(S) > 2\Delta(Q) $$

Compute the DT directly on the surface

Insert input points

Remove the points of $Q$ if possible

<figure><img src="image_110.png" /></figure>

3D cubic flat torus [Caroli T. CGAL'09]

2D square flat torus [Kruithof CGAL'13]

Bolza surface [Iordanov T. CGAL'19]
Initialize the Delaunay triangulation in $\mathbb{H}^2$ with $Q$ s.t.

$$ sys(S) > 2\Delta(Q) $$

Compute the DT directly on the surface

Insert input points

Remove the points of $Q$ if possible

Questions

$sys(S)$?

Algorithms computing $Q$?

High degree algebraic numbers

Number of points in $Q$?

Bounds for generalized Bolza surfaces

[ Ebbens Iordanov T. Veger JoCG'22 ]
Initialize the Delaunay triangulation in $\mathbb{H}^2$ with $Q$

$$ sys(S) > 2\Delta(Q) $$

Compute the DT directly on the surface in $\mathbb{H}^2$

Insert input points

Remove the points of $Q$ if possible

Project to the surface
Initialize the Delaunay triangulation in $H^2$ with $Q$

$$ sys(S) > 2\Delta(Q) $$

Compute the DT directly on the surface in $H^2$

Insert input points

Remove the points of $Q$ if possible

Project to the surface

Questions

How far do we need to go?

How many copies of points do we need?
knowing a Dirichlet domain

flat torus: $\le 13$

lattice reduction

[ Dolbilin Huson 1997 ]

project as soon as

validity condition holds

[ Osang Rouxel-Labbé T. ESA'20 ]

[ Osang Rouxel-Labbé T. CGAL To Appear ]

<figure><img src="image_111.png" /></figure>

Questions

How far do we need to go?

How many copies of points do we need?
knowing a Dirichlet domain

flat torus: $\le 13$

lattice reduction

[ Dolbilin Huson 1997 ]

project as soon as

validity condition holds

[ Osang Rouxel-Labbé T. ESA'20 ]

[ Osang Rouxel-Labbé T. CGAL To Appear ]

general hyperbolic surface:

$O((12g)^{12g-6})$

[ Despré Kolbe T. HAL'20 ]

## Questions

How far do we need to go?

How many copies of points do we need?

<figure><img src="image_112.png" /></figure>
Flip algorithm on a surface
<figure><img src="image_113.png" /></figure>
<figure><img src="image_114.png" /></figure>

propagate flips
A stronger result

$n$ points in $\mathbb{R}^2$

The flip graph of

triangulations is connected

<figure><img src="image_115.png" /></figure>

[ Hurtado *et al.* DCG’99 ]
A stronger result

<figure><img src="image_116.png" /></figure>

The **flip graph** of **geometric** triangulations is connected

<figure><img src="image_117.png" /></figure>

The Delaunay triangulation is geometric

[ Despré Schlenker T. SoCG'20 ]
<figure><img src="image_118.png" /></figure>

smallest diameter
of a connected
union of lifts
$\tilde{t} \in \pi^{-1}(t), t \in T$

$\Omega$ fundamental domain
# Diameter

A flip can never create an edge longer than $2D(T)$

Proof
# Diameter

A flip can never create an edge longer than $2D(T)$

## Proof

$v$ on the surface, $\tilde{v} \in \pi^{-1}(v)$, $z=1$

<figure><img src="image_119.png" /></figure>

stereographic projection

[ Despré Schlenker T. SoCG'20 ]
# Diameter

A flip can never create an edge longer than $2D(T)$

Proof

<figure><img src="image_120.png" /></figure>

[ Despré Schlenker T. SoCG’20 ]
# Diameter

A flip can never create an edge longer than $2D(T)$

Proof

<figure><img src="image_121.png" /><figcaption>stereographic projection</figcaption></figure>

[ Despré Schlenker T. SoCG'20 ]

flip in $\mathbb{H}^2$

<figure><img src="image_122.png" /></figure>

after

4 points on $\mathbb{S}^2$

Delaunay $\leftrightarrow$ convex polyhedron
an edge can never reappear
A flip can never create an edge longer than $2D(T)$

## Proof

$v$ on the surface, $\tilde{v} \in \pi^{-1}(v) \ z = 1$

<figure><img src="image_123.png" /></figure>

stereographic projection

[ Despré Schlenker T. SoCG'20 ]

flip in $\mathbb{H}^2$

4 points on $\mathbb{S}^2$

<figure><img src="image_124.png" /></figure>

after

Delaunay $\leftrightarrow$ convex polyhedron
an edge can never reappear

sequence of flips

$\rightsquigarrow$ sequence of surfaces

$\Sigma_0 \subset \dots \subset \Sigma_k \subset \dots$
A flip can never create an edge longer than $2D(T)$

Proof

$\tilde{e}$ edge of $T_k$ longer than $2D(T)$

<figure><img src="image_125.png" /></figure>
A flip can never create an edge longer than $2D(T)$

Proof

$\tilde{e}$ edge of $T_k$ longer than $2D(T)$

<figure><img src="image_126.png" /></figure>
<figure><img src="image_127.png" /></figure>

$w(T) = \sum_{t \in T} (\text{number of points in } \text{open\_disk}(t))$ all disks are compact
<figure><img src="image_128.png" /></figure>
$\mathbb{T}_u$, $n$ points, triangulation $T$

$C_u \cdot D(T) \cdot n^2$ flips to the Delaunay triangulation

[ Dubois CCCG'22 ]
Proof

in $\mathbb{H}^2$

$$w(T) = \sum_{t \in T} \left( \begin{array}{c} \text{number of points} \\ \text{in disk}(t) \end{array} \right)$$

disks not always compact

<figure><img src="image_129.png" /></figure>

[ Despré Schlenker T. SoCG'20 ]
Proof

in $\mathbb{H}^2$

$$w(T) = \sum_{t \in T} \left( \text{number of points in disk}(t) \right)$$

disks not always compact

edges are shorter than $2D(T)$

<figure><img src="image_130.png" /></figure>

compact disk

(but area is exponential)

finite number of possible edges

⇒ termination

⇒ connectivity

<figure><img src="image_131.png" /></figure>

[ Despré Schlenker T. SoCG'20 ]
surface $S$, $n$ points, triangulation $T$
$\le C_{\text{metric}} \cdot D(T)^{6g-4} \cdot n^2$ flips to the Delaunay triangulation
surface $S$, $n$ points, triangulation $T$
$\le C_{\text{metric}} \cdot D(T)^{6g-4} \cdot n^2$ flips to the Delaunay triangulation

Sketch of proof

count non-homotopic simple **paths**
known: closed curves
[ Fathi Laudenbach Poénaru SMF '79 ]
surface $S$, $n$ points, triangulation $T$
$\le C_{\text{metric}} \cdot D(T)^{6g-4} \cdot n^2$ flips to the Delaunay triangulation

Sketch of proof

<figure><img src="image_132.png" /><figcaption>[ Despré Schlenker T. SoCG'20 ]</figcaption></figure>

count non-homotopic simple **paths**

known: closed curves

[ Fathi Laudenbach Poénaru SMF'79 ]

path $f = (v_1, v_2)$

normal form homotopic to $f$

$f = (v_1, w_1) \cup (w_1, w_2) \cup (w_2, v_2)$

$w_i$ on annulus boundary

“push” twists in annuli

“normal” coordinates

w.r.t. short pants
surface $S$, $n$ points, triangulation $T$
$\le C_{\text{metric}} \cdot D(T)^{6g-4} \cdot n^2$ flips to the Delaunay triangulation

Sketch of proof

<figure><img src="image_133.png" /></figure>

bound on length = $6g - 4$ Dehn Thurston coordinates
count possible coordinates and possible paths

<figure><img src="image_134.png" /></figure>
surface $S$, $n$ points, triangulation $T$
$\le C_{\text{metric}} \cdot D(T)^{6g-4}$. $n^2$ flips to the Delaunay triangulation

Is the bound (close to) tight?

Experimental analysis
<figure><img src="image_135.png" /><figcaption>admissible symmetric octagon</figcaption></figure>

[ Aigon-Dupuy, Buser, etc Math. Phys.'05 ]

<figure><img src="image_136.png" /></figure>

[ Despré Dubois Kolbe T. HAL'21 ]
[ Despré Dubois Kolbe T. HAL'21 ]

<figure><img src="image_137.png" /></figure>

triangulation
[ Despré Dubois Kolbe T. HAL'21 ]

<figure><img src="image_138.png" /><figcaption>triangulation</figcaption></figure>

combinatorial map

<figure><img src="image_139.png" /></figure>

[ Damiand ]
[ Despré Dubois Kolbe T. HAL'21 ]

<figure><img src="image_140.png" /><figcaption>triangulation</figcaption></figure>

combinatorial map

<figure><img src="image_141.png" /></figure>

CGAL

[ Damiand ]

<figure><img src="image_142.png" /></figure>

forget points
maintain cross-ratios

$$[u_1, u_2, u_3, u_4] = \frac{(u_4 - u_2)(u_3 - u_1)}{(u_4 - u_1)(u_3 - u_2)}$$
[ Despré Dubois Kolbe T. HAL'21 ]

Practical issue

high degree algebraic numbers

<figure><img src="image_143.png" /></figure>

forget points

maintain cross-ratios

$$[u_1, u_2, u_3, u_4] = \frac{(u_4-u_2)(u_3-u_1)}{(u_4-u_1)(u_3-u_2)}$$
[ Despré Dubois Kolbe T. HAL'21 ]

Practical issue

high degree algebraic numbers

Density result

Given: admissible $(z_0, z_1, z_2, z_3)$ and $\varepsilon > 0$

∃ **rational admissible** $(\mathbf{z}_0, \mathbf{z}_1, \mathbf{z}_2, \mathbf{z}_3)$
$\forall k, \mathbf{z}_k \in B(z_k, \varepsilon)$
Dependence on diameter

surface $S$, $n$ points, triangulation $T$
$\le C_{\text{metric}} \cdot D(T)^{6g-4}$. $n^2$ flips to the Delaunay triangulation

need triangulations with large diameter

<figure><img src="image_144.png" /></figure>

use Dehn twists
# Dependence on diameter

surface $S$, $n$ points, triangulation $T$
$\le C_{\text{metric}} \cdot D(T)^{6g-4}$. $n^2$ flips to the Delaunay triangulation

need triangulations with large diameter

<figure><img src="image_145.png" /></figure>

use **Dehn twists** along **side pairings**

<figure><img src="image_146.png" /></figure>

same surface, larger diameter
[ Despré Dubois Kolbe T. HAL'21 ]

2 types

Power sequences of twists

Random sequences of twists

on a large number of octagons
## number of flips

[ Despré Dubois Kolbe T. HAL'21 ]

<figure><img src="image_147.png" /></figure>

**linear behavior:**

flips untwist the triangulation

by a constant number of flips per iteration of the twist
number of flips

[ Despré Dubois Kolbe T. HAL'21 ]

<figure><img src="image_148.png" /></figure>
number of flips

[ Despré Dubois Kolbe T. HAL'21 ]

<figure><img src="image_149.png" /></figure>

logarithmic behavior

“looks like” M. Bell’s results

(topological triangulations)
# Questions

$S_g$ topological surface

$\text{Mod}(S_g)$ = mapping class group

= set of homeomorphisms (up to isotopy) of $S_g$
# Questions

$S_g$ topological surface

$\text{Mod}(S_g)$ = mapping class group
= set of homeomorphisms (up to isotopy) of $S_g$

[ Disarlo Parlier T.AMS'19 ]

Flip graph quasi isometric to $\text{Mod}(S_g)$
# Questions

$S_g$ topological surface

$$ \begin{aligned} \mathrm{Mod}(S_g) &= \text{mapping class group} \\ &= \text{set of homeomorphisms (up to isotopy) of } S_g \end{aligned} $$

[ Thurston ]

reducible: fix at least one curve

pseudo-Anosov (hyperbolic)

periodic (finite order)
# Questions

$S_g$ topological surface

$$ \begin{aligned} \mathrm{Mod}(S_g) &= \text{mapping class group} \\ &= \text{set of homeomorphisms (up to isotopy) of } S_g \end{aligned} $$

[ Thurston ]

reducible: fix at least one curve

Dehn twists

<figure><img src="image_150.png" /></figure>

asymptotically

add a constant to the length

<figure><img src="image_151.png" /></figure>

pseudo-Anosov (hyperbolic)

multiply the length by a constant

periodic (finite order)
# Questions

$S_g$ topological surface

$\text{Mod}(S_g)$ = mapping class group
= set of homeomorphisms (up to isotopy) of $S_g$

$\text{Mod}(S_g)$ generated by a finite set of

<figure><img src="image_152.png" /><figcaption>Dehn twists</figcaption></figure>

[ Farb Margalit '12 ]

<figure><img src="image_153.png" /></figure>

random composition $\rightsquigarrow$ random walk in $\text{Mod}(S_g)$
pseudo-Anosov with asymptotic probability 1

[ Maher Duke'11 ]
# Questions

$S_g$ topological surface

$$ \begin{aligned} \mathrm{Mod}(S_g) &= \text{mapping class group} \\ &= \text{set of homeomorphisms (up to isotopy) of } S_g \end{aligned} $$

[ Bell DCG'21]

effect on the flip graph of topological triangulations
a pseudo-Anosov or a power of a Dehn twist
reduces the **number of crossings** with a **fixed** curve

different problem here
**unknown goal (Delaunay)**
how far from the goal?
homotopy class of goal edges?
surface $S$, $n$ points, triangulation $T$ [Despré Dubois Kolbe T. HAL'21]

\# flips to the Delaunay triangulation?

On our experiments ($g = 2$)

$$ \leq C_{\text{metric}} \cdot D(T) \cdot n^2 $$

<figure><img src="image_154.png" /></figure>

average (?) $\log(D(T))$
surface $S$, $n$ points, triangulation $T$ [Despré Dubois Kolbe T. HAL'21]

\# flips to the Delaunay triangulation?

On our experiments ($g = 2$)

$$ \le C_{\text{metric}} \cdot D(T) \cdot n^2 $$

<figure><img src="image_155.png" /></figure>

average (?) $\log(D(T))$

so...?
surface $S$, $n$ points, triangulation $T$ [Despré Dubois Kolbe T. HAL'21]

\# flips to the Delaunay triangulation?

On our experiments ($g = 2$)

$$ \le C_{\text{metric}} \cdot D(T) \cdot n^2 $$

<figure><img src="image_156.png" /></figure>

average (?) $\log(D(T))$

so...?

other input surfaces ?
Thank you!
(Slides just in case)
Before CGAL, in Europe

PlaGeo, SpaGeo (Utrecht)

XYZ GeoBench (ETH Zürich)

LEDA (MPII Saarbrücken)

C++GAL
(INRIA Sophia Antipolis)

...

<figure><img src="image_157.png" /><figcaption>Jodelet/Lépinay - CC Attribution-Share Alike 2.0 France</figcaption></figure>
1995 - Start: Gather efforts

Academic consortium

<figure><img src="image_158.png" /></figure>
**1995 - Start: Gather efforts**

Academic consortium

**2003**

**Open Source project**

Double-license: GPLv3+ and commercial
new contributors

**Creation of**

<figure><img src="image_159.png" /></figure>

Geometry
Factory

initially as an INRIA startup

sells commercial licenses and pays royalties to owners
responsible for the infrastructure
and long-term evolutive maintenance
## Promote research in CG

"make the large body of geometric algorithms developed in the field of computational geometry available for industrial applications"

⇒ high quality review process, ...

⇒ robust code
Promote research in CG

Reward structure for implementations in academia

⇒ high quality
review process, ...

⇒ robust code
http://www.cgal.org

Many platforms

Linux, MacOS, Windows

g++, VC++,clang,...
http://www.cgal.org

Many platforms

Linux, MacOS, Windows

g++, VC++,clang,...

Download from github

or use

Linux distribution (Debian,...)

Mac distribution (macports, brew,...)

Euclidean 2D and 3D triangulations

* in Matlab

* in Python through CGAL bindings
http://www.cgal.org

Follow “Getting started”

easier than ever!

* “Since CGAL version 5.0, CGAL is header-only by default, which means that there is no need to build CGAL before it can be used.”

* Simple viewer
http://www.cgal.org

Follow “Getting started”

Read the **User manual** of your favorite package

Read, compile and run **examples**
<figure><img src="image_160.png" /></figure>

http://www.cgal.org

Follow "Getting started"

Read the **User manual** of your favorite package

Read, compile and run **examples**

**Write your own code!**

looking at the **Reference manual**

Obey license `GPLv3+` (or buy a commercial license)
<figure><img src="image_161.png" /></figure>

http://www.cgal.org

Molecular Modeling

Particle Physics, Fluid Dynamics, Microstructures

Medical Modeling and Biophysics

Geographic Information Systems

Games

Motion Planning

Sensor Networks

Architecture, Buildings Modeling, Urban Modeling

Astronomy

2D and 3D Modelers

Mesh Generation and Surface Reconstruction

Geometry Processing

Computer Vision, Image Processing, Photogrammetry

Computational Topology and Shape Matching

Computational Geometry and Geometric Computing
# Becoming a CGAL user

## some commercial users (2012)

<figure><img src="image_162.png" /></figure>
Ipelets!

ipe.otfried.org/
<figure><img src="image_163.png" /></figure>

Ipelets!

ipe.otfried.org/

Generators

e.g. 200 points in a disk

R²

<figure><img src="image_164.png" /></figure>
Ipelets!

ipe.otfried.org/

Generators

e.g. 200 points in a disk

R²

“Diagrams”

→ Voronoi

<figure><img src="image_165.png" /></figure>
<figure><img src="image_166.png" /></figure>

**Ipelets!**

ipe.otfried.org/

**Generators**

e.g. 200 points in a disk

$\mathbb{R}^2$

**“Triangulations”**
→ Delaunay

<figure><img src="image_167.png" /></figure>