# Triangulations of Closed Surfaces

A triangulation of a closed surface is composed of points on the closed surface, which are connected by a maximal number of arcs (isotopy classes of curves on the surface that start and end at fixed points without containing any loops) in such a way, that no two arcs are homotopic to each other.

As these become very complex objects that are difficult and computationally complex to model, it is often more useful to look at the dual of a triangulation. This dual is called a *Δ-complex*.

## DeltaComplex

A **Δ-complex** is a representation of a triangulation on a closed surface. To define a triangulation on a closed surface, it does not suffice to consider vertices and edges. We will also need to consider the triangular faces between them. Therefore, the triangulations are modeled using an extension of their dual graph.

Vertices are triangular faces, which in turn consist of three points and three edges. These points and edges are not necessarily distinct. Edges in the dual (i.e. the Δ-complex) connect two triangular faces if they, in turn, share an edge. In order to avoid confusion between the edges of the triangulation and the edges of the dual, I will henceforth refer to the latter as the *dual edge*.

### Structures

`FlipGraphs.DeltaComplex`

— Type`struct DeltaComplex`

A graph data structure representing a triangulation of a surface.

The `DeltaComplex`

may be thought of as the dual of a triangulation.

Vertices are triangular faces (`TriFace`

). Every vertex has three edges (`DualEdge`

) incident to it.

`FlipGraphs.TriFace`

— Type`struct TriFace`

A `TriFace`

represents a triangle in the triangulization of a surface.

The `TriFace`

s form the vertices of a DeltaComplex. Each `TriFace`

is formed between 3 points and is connected to 3 `TriFace`

s through `DualEdges`

. The points and neighboring triangles do not have to be unique.

The points and edges are stored in an anticlockwise order.

The first edge/side is between the first and second point.

The second edge/side is between the second and third point.

The third edge/side is between the third and first point.

`FlipGraphs.DualEdge`

— Type`struct DualEdge`

Representation of an edge in a DeltaComplex (i.e. the dual graph of a triangulation).

A DualEdge connects two TriFaces through specific sides.

### Construction of a DeltaComplex

This Module comes with some handy and easy to use tools to construct a triangulation of a surface:

`FlipGraphs.deltacomplex`

— Function`deltacomplex(genus :: Integer, num_points :: Integer = 1) :: DeltaComplex`

Create a triangulation of an orientable surface of a certain `genus`

with `num_points`

points on it.

By default, `num_points`

is set to 1.

`deltacomplex(s :: Vector{<:Integer})`

Create a triangulation of an orientable surface with a single point, by gluing the corresponding edges together.

`s`

should be an array of nonzero integers representing the edges of a polygon in anticlockwise order.

The i-th edge is orientated anticlockwise if `s[i]>0`

and anticlockwise if `s[i]<0`

.

If `s[i]`

and `s[j]`

have the same absolute value, they are glued together while respecting their orientation.

**Examples**

The following results in the triangulation of a *torus* with one point:

`julia> deltacomplex([1,2,-1,-2])`

The following results in the triangulation of a *klein bottle* with one point:

`julia> deltacomplex([1,2,-1,2])`

`FlipGraphs.deltacomplex_non_orientable`

— Function`deltacomplex_non_orientable(demigenus :: Integer, num_points :: Integer = 1) :: DeltaComplex`

Create a triangulation of a non-orientable surface with `num_points`

points on it.

By default, `num_points`

is set to 1.

`FlipGraphs.subdivide!`

— Method`subdivide!(D::DeltaComplex, t::Integer)`

Add a point to the inside of the `t`

-th `TriFace`

and connect it to each corner.

### Extracting information from `DeltaComplex`

'

`DeltaComplex`

is not an implementation of *Graphs.AbstractGraph*. However, as it is similar to a simple graph, the same notation and function names were used for simplicity.

`FlipGraphs.np`

— Method`np(D::DeltaComplex) :: Int`

Return the number of points in the triangulation defined by `D`

.

`Graphs.nv`

— Method`nv(D::DeltaComplex) :: Int`

Return the number of vertices (`TriFace`

s) in `D`

.

`Graphs.ne`

— Method`ne(D::DeltaComplex) :: Int`

Return the number of edges (`DualEdge`

s) in the `DeltaComplex`

`D`

.

This is equal to the number of edges in the triangulation itself.

`Graphs.vertices`

— Method`vertices(D::DeltaComplex) :: Vector{TriFace}`

Return the list of all vertices(`TriFace`

s) in `D`

.

`FlipGraphs.get_vertex`

— Method`get_vertex(D::DeltaComplex, t::Integer) :: TriFace`

Return the `t`

-th `TriFace`

in `D`

`Graphs.edges`

— Method`edges(D::DeltaComplex) :: Vector{DualEdge}`

Return the list of all the `DualEdge`

s in `D`

.

`FlipGraphs.get_edge`

— Method`get_edge(D::DeltaComplex, e::Integer) :: DualEdge`

Return the `e`

-th `DualEdge`

in the `DeltaComplex D`

.

`FlipGraphs.get_edge`

— Method`get_edge(D::DeltaComplex, t::Integer, side::Integer) :: DualEdge`

Return the edge that forms the respective `side`

(1,2 or 3) of the `t`

-th `TriFace`

in the given `DeltaComplex`

.

`FlipGraphs.quadrilateral_edges`

— Method`quadrilateral_edges(D::DeltaComplex, diagonal::DualEdge) :: Tuple{DualEdge, DualEdge, DualEdge, DualEdge}`

Return the 4 edges who form a quadrilateral with the given `diagonal`

.

`FlipGraphs.is_similar`

— Method`is_similar(d1::DualEdge, d2::DualEdge) :: Bool`

Return `true`

if d1 and d2 have the same twist and are connected to the same triangles.

This is only the case if `d1`

and `d2`

are the same edge, or if they are incident to a point of degree 2.

### Extracting information from `TriFace`

s

`TriFace`

s form the vertices of a `DeltaComplex`

. They are defined by their 3 edges. Additionally, they store the 3 points that form their corners.

As the `TriFace`

s are stored in a list in `DeltaComplex`

, each `TriFace`

has its proper `id`

which is the same as its index in the list.

`FlipGraphs.id`

— Method`id(T::TriFace) :: Int`

Return the index of the triangular face `T`

in its `DeltaComplex`

.

If you wish to get the edges of a `TriFace`

, you might want to use any of the following methods:

`FlipGraphs.get_edge`

— Method`get_edge(T::TriFace, side::Integer) :: DualEdge`

Return the `DualEdge`

that is incident to the given `side`

(1, 2 or 3) of the triangular face `T`

.

`FlipGraphs.get_edge_id`

— Method`get_edge_id(T::TriFace, side::Integer) :: Integer`

Return the index of the `DualEdge`

s on the respective `side`

(1, 2 or 3) of the triangular face `T`

.

`Graphs.edges`

— Method`edges(T::TriFace) :: Vector{DualEdge}`

Return the list of all 3 `DualEdge`

s that are incident to the triangular face `T`

.

`FlipGraphs.edges_id`

— Method`edges_id(T::TriFace) :: Tuple{Int, Int, Int}`

Return the indices of all 3 `DualEdge`

s that are incident to the `TriFace T`

.

`Graphs.edges`

— Method`edges(D::DeltaComplex, t::Integer) :: Vector{DualEdge}`

Return the list of all 3 `DualEdge`

s that are incident to the `t`

-th `TriFace`

in `D`

.

`FlipGraphs.edges_id`

— Method`edges_id(D::DeltaComplex, t::Integer) :: Tuple{Int, Int, Int}`

Return the indices of all 3 `DualEdge`

s that are incident to the `t`

-th `TriFace`

in `D`

.

If you wish to get the points that form the corners of a `TriFace`

, you might want to use any of the following methods:

`FlipGraphs.has_point`

— Method`has_point(T::TriFace, x::Integer) :: Bool`

Return `true`

if `x`

forms one of the corners of the triangular face `T`

`FlipGraphs.get_point`

— Method`get_point(T::TriFace, corner::Integer) :: Int`

Return the point that is at the given `corner`

(1, 2 or 3) of the triangular face `T`

.

`FlipGraphs.points`

— Method`points(T::TriFace) :: Tuple{Int, Int, Int}`

Return a tuple of the three points, that form the corners of `T`

.

`FlipGraphs.points`

— Method`points(D::DeltaComplex, d::DualEdge) :: Tuple{Int, Int}`

Return both endpoints of the edge `d`

in the triangulation defined by `D`

.

### Extracting information from `DualEdge`

s

`DualEdge`

s form the edges in a `DeltaComplex`

. They are defined by the 2 triangles that form the endpoints and the respective sides through which they connect them. In addition, they may be twisted. (See Non-orientable closed surfaces for more on twisted edges) Contrary to a normal graph, it is important on which side of a `TriFace`

an edge is incident to.

Like the `TriFace`

s, `DualEdge`

s are also stored in a list in `DeltaComplex`

, each `DualEdge`

has its proper `id`

which is the same as its index in the list.

`FlipGraphs.id`

— Method`id(d::DualEdge) :: Int`

Return the index of `d`

in its `DeltaComplex`

.

If you wish to get the `TriFace`

s that border the `DualEdge`

, you might want to use any of the following methods:

`Graphs.vertices`

— Method`vertices(D::DeltaComplex, d::DualEdge) :: Tuple{TriFace, TriFace}`

Return both vertices(`TriFace`

s) adjacent to the dual edge `d`

.

The first `TriFace`

is on the left of the edge, and the second one on the right of the edge.

`FlipGraphs.vertices_id`

— Method`vertices_id(d::DualEdge) :: Tuple{Int, Int}`

Return the indices of both vertices (`TriFace`

s) adjacent to `d`

.

`FlipGraphs.get_vertex_id`

— Method`get_vertex_id(d::DualEdge, side::Integer) :: Int`

Return the index of the vertex (`TriFace`

) to the left of `d`

.

`FlipGraphs.sides`

— Function`sides(d::DualEdge) :: Tuple{Int8, Int8}`

Return the respective sides through which `d`

connects its incident `TriFace`

s.

`FlipGraphs.get_side`

— Method`get_side(d::DualEdge, side::Integer) :: Int8`

Return the respective side of the triangle that `d`

forms on the `TriFace`

on the given `side`

of `d`

.

`FlipGraphs.other_endpoint`

— Method`other_endpoint(d::DualEdge, t::Integer, side::Integer) :: Tuple{Int, Int8}`

Return the index of the other TriFace and its respective side, that is incident to `d`

## Classifying the triangulation

Here are some useful methods, to pull out general information about the Δ-Complex, and the triangulation it represents:

`FlipGraphs.genus`

— Method`genus(D::DeltaComplex) :: Int`

Compute the *genus* of the `DeltaComplex`

`D`

if it forms an orientable surface.

`FlipGraphs.euler_characteristic`

— Method`euler_characteristic(D::DeltaComplex) :: Int`

Compute the *euler characteristic* of the `DeltaComplex D`

:

\[X = n_{vertices} - n_{edges} + n_{faces} \]

`FlipGraphs.diameter_triangulation`

— Method`diameter_triangulation(D::DeltaComplex)`

Compute the diameter of the triangulation defined by the DeltaComplex `D`

.

The **diameter** of a graph is the greatest minimal distance between any 2 vertices.

See also `diameter_deltaComplex`

`FlipGraphs.diameter_deltaComplex`

— Method`diameter_deltacomplex(D::DeltaComplex)`

Compute the *diameter* of the `DeltaComplex`

`D`

.

The **diameter** of a graph is the greatest minimal distance between any 2 vertices.

See also `diameter_triangulation`

`FlipGraphs.diameter`

— Method`diameter(D::DeltaComplex)`

Compute the diameter of the DeltaComplex `D`

.

The **diameter** of a graph is the greatest minimal distance between any 2 vertices.

See also `diameter_triangulation`

`FlipGraphs.adjacency_matrix_deltacomplex`

— Method`adjacency_matrix_deltacomplex(D::DeltaComplex) :: Matrix{::Int32}`

Compute the *adjacency matrix* of the delta complex `D`

.

`FlipGraphs.adjacency_matrix_triangulation`

— Method`adjacency_matrix_triangulation(D::DeltaComplex) :: Matrix{Int32}`

Compute the *simple adjacency matrix* of the triangulation defined by `D`

.

All entries are either 0 or 1.

See also `multi_adjacency_matrix_triangulation`

`FlipGraphs.multi_adjacency_matrix_triangulation`

— Method`multi_adjacency_matrix_triangulation(D::DeltaComplex) :: Matrix{Int32}`

Compute the *adjacency matrix* of the multigraph of the triangulation defined by `D`

.

The $i,j$-th entry notes the number of edges that connect these two points.

See also `adjacency_matrix_triangulation`

`FlipGraphs.point_degrees`

— Method`point_degrees(D::DeltaComplex) :: Vector{<:Integer}`

Return a vector containing the respective degree of each point in the triangulation.

### Relabeling

If you wan't to relabel/reorder the points vertices or edges, you may do so, by providing a permutation vector $p=[p_1, p_2, \ldots , p_n]$ which will relabel $i$ as $p_i$.

`FlipGraphs.rename_edges!`

— Method`rename_edges!(D::DeltaComplex, p::Vector{<:Integer})`

Relabel every edge(`DualEdge`

) in `D`

, according to the permutation `p`

.

`DualEdge`

1 => `DualEdge`

$p[1]$

`FlipGraphs.rename_points!`

— Method`rename_points!(D::DeltaComplex, p::Vector{<:Integer})`

Rename all the points in `D`

according to the permutation `p`

.

`FlipGraphs.rename_vertices!`

— Method`rename_vertices!(D::DeltaComplex, p::Vector{<:Integer})`

Relabel every vertex(`TriFace`

) in `D`

, according to the permutation `p`

.

`TriFace`

1 => `TriFace`

$p[1]$

## Non-orientable closed surfaces

Regarding on how different sides of triangles are associated to each other, the resulting surface may be non-orientable. These surfaces can also be modeled by `DeltaComplex`

, and all the methods above (except for `genus`

) may still be applied.

`FlipGraphs.is_orientable`

— Method`is_orientable(D::DeltaComplex) :: Bool`

Ckeck if the surface defined by `D`

is orientable or not.

`FlipGraphs.demigenus`

— Function`demigenus(D::DeltaComplex) :: Int`

Compute the *demigenus* of the `DeltaComplex`

`D`

if it is non-orientable.

The **demigenus** or **non-orientable genus** ($k$) of a connected non-orientable closed surface is defined via the euler characteristic ($X$) :

$k = 2 - X$

`FlipGraphs.twist_edges!`

— Function```
twist_edges!(D::DeltaComplex, t::Integer)
twist_edges!(T::TriFace)
```

Twist or untwist all 3 `DualEdges`

of a `TriFace`

, and reverse the side order.

This action gives an equivalent representation ot the same triangulation. It is usefull in the case that you would like to untwist a certain edge.

**Examples**

```
julia> D = deltacomplex([1,2,-1,2]);
julia> T = get_vertex(D,1);
julia> edges(T)
3-element Array{DualEdge,1}:
DualEdge 2 : (Δ1)-(1)-------(2)-(Δ2)
DualEdge 1 : (Δ1)-(2)-------(3)-(Δ2)
DualEdge 3 : (Δ2)-(1)---↺---(3)-(Δ1)
julia> twist_edges!(T);
julia> edges(T)
3-element Array{DualEdge,1}:
DualEdge 3 : (Δ2)-(1)-------(1)-(Δ1)
DualEdge 1 : (Δ1)-(2)---↺---(3)-(Δ2)
DualEdge 2 : (Δ1)-(3)---↺---(2)-(Δ2)
```

`FlipGraphs.is_twisted`

— Function`is_twisted(d::DualEdge) :: Bool`

Return whether or not the given edge is twisted.

If `d`

is twisted, then everything on the other side gets regarded as its mirror image.

## Flipping

A **flip** is defined as the action of replacing an edge in the triangulation by the other diagonal of the quadrilateral formed by the two triangles adjacent to the edge.

It has been shown, that the flip graph of any closed surface is connected. Hence it is possible, to obtain any triangulation by a finite number of flips.

`FlipGraphs.flip`

— Method`flip(D::DeltaComplex, e::Integer) :: DeltaComplex`

Return the resulting `DeltaComplex`

obtained by flipping the given edge in `D`

.

`FlipGraphs.flip!`

— Method`flip!(D::DeltaComplex, e::Integer)`

Flip, if possible, the given edge in `D`

.

`FlipGraphs.flip!`

— Method`flip!(D::DeltaComplex, d::DualEdge)`

Flip, if possible, the given edge in `D`

.

`FlipGraphs.is_flippable`

— Method`is_flippable(D::DeltaComplex, e::Integer) :: Bool`

Return `true`

if the given edge can be flipped.

This is always the case if the edge does not connect a `TriFace`

to itself.

`FlipGraphs.is_flippable`

— Method`is_flippable(d::DualEdge)`

Return `true`

if the given edge is can be flipped.

This is always the case if the edge does not connect a `TriFace`

to itself.

`FlipGraphs.random_flips!`

— Method`random_flips!(D::DeltaComplex, n::Integer)`

Randomly pick an edge, and flip it if possible. Repeat this `n`

times.

`FlipGraphs.randomize!`

— Method`randomize!(D::DeltaComplex; kwargs...) -> Int`

Randomly flip edges in `D`

until `D`

is sufficiently generic and return the number of attempted flips.

The measure by which we determin if `D`

is sufficiently generic is through its diameter. This Method repeatedly flips a certain number of times. After each flip sequence, the diameter is computed. Once this was repeated a certain number of times, the variance of all these past diameter measurements gets computed.

In theory, the variance should diminish over time. However, as we are flipping randomly, it will never truly converge to 0. A certain flutter in the variance is expected, this will at some point cause the variance to increase every so often. The algorithm stops once the last measured variance is bigger than the past few measurements.

**Arguments**

`num_initial_flips::Integer=1000000`

: the number of flips to do before even start taking measurements.`num_flips_per_step::Integer=10000`

: the number of flips to do before computing the diameter each step.`variance_interval_size::Integer=10`

: the number of diameters to store, before computing their variance.`lookback_size::Integer=2`

: how far back to compare the current variance to, in order to decide when to stop.

**Examples**

```
julia> D = deltacomplex(30,30);
julia> randomize!(D, num_initial_flips=10000, num_flips_per_step = 1000, variance_interval_size=10, lookback_size = 5)
160000
```