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. 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 triangulation of a surface.

The TriFaces form the vertices of a DeltaComplex. Each TriFace is formed between 3 points and is connected to 3 TriFaces 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 (TriFaces) in D.

Graphs.ne — Method
ne(D::DeltaComplex) :: Int

Return the number of edges (DualEdges) 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(TriFaces) 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 DualEdges 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 TriFaces

TriFaces 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 TriFaces 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 DualEdges 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 DualEdges 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 DualEdges that are incident to the TriFace T.

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

Return the list of all 3 DualEdges 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 DualEdges 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 DualEdges

DualEdges 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 TriFaces, DualEdges 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 TriFaces 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(TriFaces) 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 (TriFaces) 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 TriFaces.

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 — 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 simple adjacency matrix of the delta complex D.

Values are either 0(not adjacent) or 1(adjacent).

FlipGraphs.multi_adjacency_matrix_deltacomplex — Method
multi_adjacency_matrix_deltacomplex(D::DeltaComplex) :: Matrix{Int32}

Compute the multi adjacency matrix of the delta complex D.

The i,j-th value counts the number of sides through which the i-th and j-th TriFace are adjacent.

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 want 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

Check 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 of the same triangulation. It is useful 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 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 determine 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