Effective Computational Geometry
for Curves and Surfaces
Chapter 7
Computational Topology: An Introduction
Gu¨nter Rote and Gert Vegter
We give an introduction to combinatorial topology, with an emphasis on subjects that are
of interest for computational geometry in two and three dimensions. We cover the notions of
homotopy and isotopy, simplicial homology, Betti numbers, and basic results from Morse Theory.
This survey appeared as a chapter of the book Effective Computational Geometry for Curves
and Surfaces, (Jean-Daniel Boissonnat, Monique Teillaud, editors), published by Springer-Verlag,
2007, ISBN 3-540-33258-8. Page references to other chapters are to the pages of the book. The
original publication is available on-line at www.springerlink.com.
Contents
1 Arrangements
2 Curved Voronoi Diagrams
3 Algebraic Issues in Computational Geometry
4 Differential Geometry on Discrete Surfaces
5 Meshing of Surfaces
6 Delaunay Triangulation Based Surface Reconstruction
7 Computational Topology: An Introduction 1
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
7.2 Simplicial complexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
Topological spaces. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
Homeomorphisms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
Simplices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
Simplicial complexes. . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
Combinatorial surfaces. . . . . . . . . . . . . . . . . . . . . . . . . . 4
Homotopy and Isotopy: Continuous Deformations. . . . . . . . . . . 4
7.3 Simplicial homology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
A calculus of closed loops. . . . . . . . . . . . . . . . . . . . . . . . . 5
Chain spaces and simplicial homology. . . . . . . . . . . . . . . . . . 6
Example: One-homologous chains. . . . . . . . . . . . . . . . . . . . 6
Example: Zero-homology of a connected simplicial complex. . . . . . 7
Example: One-homologous chains. . . . . . . . . . . . . . . . . . . . 7
Betti numbers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Euler characteristic and Betti numbers. . . . . . . . . . . . . . . . . 10
Incremental algorithm for computation of Betti numbers. . . . . . . 10
Chain maps and chain homotopy. . . . . . . . . . . . . . . . . . . . . 12
Simplical collapse. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Example: Betti numbers of the projective plane. . . . . . . . . . . . 13
Example: Betti numbers depend on field of scalars. . . . . . . . . . . 13
7.4 Morse Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
7.4.1 Smooth functions and manifolds . . . . . . . . . . . . . . . . . . . . . . . . 14
Differential of a smooth map. . . . . . . . . . . . . . . . . . . . . . . 14
Regular surfaces in R3. . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Submanifolds of Rn. . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Tangent space of a manifold. . . . . . . . . . . . . . . . . . . . . . . 16
Smooth function on a submanifold. . . . . . . . . . . . . . . . . . . . 16
Regular and critical points. . . . . . . . . . . . . . . . . . . . . . . . 16
Implicit surfaces and manifolds. . . . . . . . . . . . . . . . . . . . . . 17
i
ii CONTENTS
Hessian at a critical point. . . . . . . . . . . . . . . . . . . . . . . . . 17
Non-degenerate critical point. . . . . . . . . . . . . . . . . . . . . . . 18
7.4.2 Basic Results from Morse Theory . . . . . . . . . . . . . . . . . . . . . . . . 18
Morse function. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
Regular level sets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
The Morse Lemma. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
Abundance of Morse functions. . . . . . . . . . . . . . . . . . . . . . 19
Passing critical levels. . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Morse inequalities. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
Gradient vector fields. . . . . . . . . . . . . . . . . . . . . . . . . . . 20
Integral lines, and their local structure near singular points. . . . . . 20
Stable and unstable manifolds. . . . . . . . . . . . . . . . . . . . . . 21
The Morse-Smale complex. . . . . . . . . . . . . . . . . . . . . . . . 22
Reeb graphs and contour trees. . . . . . . . . . . . . . . . . . . . . . 22
7.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
8 Appendix - Generic Programming and the Cgal Library
Chapter 7
Computational Topology: An
Introduction
Gu¨nter Rote, Gert Vegter1
7.1 Introduction
Topology studies point sets and their invariants under continuous deformations, invariants such
as the number of connected components, holes, tunnels, or cavities. Metric properties such as the
position of a point, the distance between points, or the curvature of a surface, are irrelevant to
topology. Computational topology deals with the complexity of topological problems, and with
the design of efficient algorithms for their solution, in case these problems are tractable. These
algorithms can deal only with spaces and maps that have a finite representation. To this end we
restrict ourselves to simplicial complexes and maps. In particular we study algebraic invariants
of topological spaces like Euler characteristics and Betti numbers, which are in general easier to
compute than topological invariants.
Many computational problems in topology are algorithmically undecidable. The mathematical
literature of the 20th century contains many (beautiful) topological algorithms, usually reducing
to decision procedures, in many cases with exponential-time complexity. The quest for efficient
algorithms for topological problems has started rather recently. The overviews by Dey, Edelsbrun-
ner and Guha [6], Edelsbrunner [7], Vegter [21], and the book by Zomorodian [22] provide further
background on this fascinating area.
This chapter provides a tutorial introduction to computational aspects of algebraic topology. It
introduces the language of combinatorial topology, relevant for a rigorous mathematical description
of geometric objects like meshes, arrangements and subdivisions appearing in other chapters of
this book, and in the computational geometry literature in general.
Computational methods are emphasized, so the main topological objects are simplicial com-
plexes, combinatorial surfaces and submanifolds of some Euclidean space. These objects are intro-
duced in Sect. 7.2. Here we also introduce the notions of homotopy and isotopy, which also feature
in other parts of this book, like Chapter 5. Most of the computational techniques are introduced
in Sect. 7.3. Topological invariants, like Betti numbers and Euler characteristic, are introduced
and methods for computing such invariants are presented. Morse theory plays an important role
in many recent advances in computational geometry and topology. See, e.g., Sect. 5.5.2. This
theory is introduced in Sect. 7.4.
Given our focus on computational aspects, topological invariants like Betti numbers are defined
using simplicial homology, even though a more advanced study of deeper mathematical aspects
of algebraic topology could better be based on singular homology, introduced in most modern
1Coordinator
1
2 CHAPTER 7. COMPUTATIONAL TOPOLOGY: AN INTRODUCTION
textbooks on algebraic topology. Other topological invariants, like homotopy groups, are harder
to compute in general; These are not discussed in this chapter.
The chapter is far from a complete overview of computational algebraic topology, and it does
not discuss recent advances in this field. However, reading this chapter paves the way for studying
recent books and papers on computational topology. Topological algorithms are currently being
used in applied fields, like image processing and scattered data interpolation. Most of these
applications use some of the tools presented in this chapter.
7.2 Simplicial complexes
Topological spaces. In this chapter a topological spaceX (or space, for short) is a subset of some
Euclidean space Rd, endowed with the induced topology of Rd. In particular, an ε-neighborhood
(ε > 0) of a point x in X is the set of all points in X within Euclidean distance ε from x. A subset
O of X is open if every point of O contains an ε-neighborhood contained in O, for some ε > 0.
A subset of X is closed if its complement in X is open. The interior of a set X is the set of all
points having an ε-neighborhood contained in X , for some ε > 0. The closure of a subset X of Rd
is the set of points x in Rd every ε-neigborhood of which has non-empty intersection with X . The
boundary of a subset X is the set of points in the closure of X that are not interior points of X .
In particular, every ε-neighborhood of a point in the boundary of X has non-empty intersection
with both X and the complement of X . See [1, Sect. 2.1] for a more complete introduction of the
basic concepts and properties of point set topology.
The space Rd is called the ambient space of X . Examples of topological spaces are:
1. The interval [0, 1] in R;
2. The open unit d-ball: Bd = {(x1, . . . , xd) ∈ Rd | x21 + · · ·+ x2d < 1};
3. The closed unit d-ball: B
d
= {(x1, . . . , xd) ∈ Rd | x21 + · · ·+ x2d ≤ 1} (the closure of Bd);
4. The unit d-sphere Sd = {(x1, . . . , xd+1) ∈ Rd+1 | x21 + · · ·+ x2d+1 = 1} (the boundary of the
(d+1)-ball);
5. A d-simplex, i.e., the convex hull of d+1 affinely independent points in some Euclidean space
(obviously, the dimension of the Euclidean space cannot be smaller than d). The number
d is called the dimension of the simplex. Fig. 7.1 shows simplices of dimensions up to and
including three.
Figure 7.1: Simplices of dimension zero, one, two and three.
Homeomorphisms. A homeomorphism is a 1–1 map h : X → Y from a space X to a space Y
with a continuous inverse. (In this chapter a map is always continuous by definition.) In this case
we say that X is homeomorphic to Y , or, simply, that X and Y are homeomorphic.
1. The unit d-sphere is homeomorphic to the subset Σ of Rm defined by Σ = {(x1, . . . , xd+1,
0, . . . , 0) ∈ Rm | x21 + · · · + x2d+1 = 1} (m > d). Indeed, the map h : Sd → Σ, defined
by h(x1, . . . , xd+1) = (x1, . . . , xd+1, 0, . . . , 0), is a homeomorphism. Loosely speaking, the
ambient space does not matter from a topological point of view.
7.2. SIMPLICIAL COMPLEXES 3
2. The map h : Rk → Rm, m > k, defined by
h(x1, . . . , xk) = (x1, . . . , xk, 0, . . . , 0),
is not a homeomorphism.
3. Any invertible affine map between two Euclidean spaces (of necessarily equal dimension) is
a homeomorphism.
4. Any two d-simplices are homeomorphic. (If the simplices lie in the same ambient space of
dimension d − 1, there is a unique invertible affine map sending the vertices of the first
simplex to the vertices of the second simplex. For other, possibly unequal dimensions of
the ambient space one can construct an invertible affine map between the affine hulls of the
simplices.)
5. The boundary of a d-simplex is homeomorphic to the unit d-sphere. (Consider a d-simplex in
Rd+1. The projection of its boundary from a fixed point in its interior onto its circumscribed
d-sphere is a homeomorphism. See Fig. 7.2. The circumscribed d-sphere is homeomorphic
to the unit d-sphere.)
p
p′
Figure 7.2: The point p on the boundary of a 3-simplex is mapped onto the point p′ on the
2-sphere. This mapping defines a homeomorphism between the 2-simplex and the 2-sphere.
Simplices. Consider a k-simplex σ, which is the convex hull of a set A of k + 1 independent
points a0, . . . , ak in some Euclidean space Rd (so d ≥ k). A is said to span the simplex σ. A
simplex spanned by a subset A′ of A is called a face of σ. If τ is a face of σ we write τ ¹ σ. The
face is proper if ∅ 6= A′ 6= A. The dimension of the face is |A′| − 1. A 0-dimensional face is called
a vertex, a 1-dimensional face is called an edge. An orientation of σ is induced by an ordering of
its vertices, denoted by 〈a0 · · ·ak〉, as follows: For any permutation pi of 0, . . . , k, the orientation
〈api(0) · · · api(k)〉 is equal to (−1)sign(pi)〈a0 · · ·ak〉, where sign(pi) is the number of transpositions
of pi (so each simplex has two distinct orientations). A simplex together with a specific choice
of orientation is called an oriented simplex. If τ is a (k−1)-dimensional face of σ, obtained by
omitting the vertex ai, then the induced orientation on τ is (−1)i〈a0 · · · aˆi · · ·ak〉, where the hat
indicates omission of ai.
Simplicial complexes. A simplicial complex K is a finite set of simplices in some Euclidean
space Rm, such that (i) if σ is a simplex of K and τ is a face of σ, then τ is a simplex of K, and
(ii) if σ and τ are simplices of K, then σ ∩ τ is either empty or a common face of σ and τ . The
dimension of K is the maximum of the dimensions of its simplices. The underlying space of K,
4 CHAPTER 7. COMPUTATIONAL TOPOLOGY: AN INTRODUCTION
denoted by |K|, is the union of all simplices of K, endowed with the subspace topology of Rm.
The i-skeleton of K, denoted by Ki, is the union of all simplices of K of dimension at most i. A
subcomplex L of K is a subset of K that is a simplicial complex. A triangulation of a topological
space X is a pair (K,h), where K is a simplicial complex and h is a homeomorphism from the
underlying space |K| to X . The Euler characteristic of a simplicial d-complex K, denoted by
χ(K), is the number
Pd
i=0(−1)iαi, where αi is the number of i-simplices of K. Examples of
simplicial complexes are:
1. A graph is a 1-dimensional simplicial complex (think of a graph as being embedded in R3).
The complete graph with n vertices is the 1-skeleton of an (n−1)-simplex.
2. The Delaunay triangulation of a set of points in general position in Rd is a simplicial complex.
Combinatorial surfaces. A Combinatorial closed surface is a finite two-dimensional simplicial
complex in which each edge (1-simplex) is incident with two triangles (2-simplices), and the set
of triangles incident to a vertex can be cyclically ordered t0, t1, . . . , tk−1 so that ti has exactly one
edge in common with ti+1modk, and these are the only common edges. Stillwell [20, page 69 ff]
contains historical background and the basic theorem on the classification combinatorial surfaces.
Homotopy and Isotopy: Continuous Deformations. Homotopy is a fundamental topo-
logical concept that describes equivalence between curves, surfaces, or more general topological
subspaces within a given topological space, up to “continuous deformations”.
Technically, homotopy is defined between two maps g, h : X → Y from a space X into a
space Y . The maps g and h are homotopic if there is a continuous map
f : X × [0, 1] → Y
such that f(x, 0) = g(x) and f(x, 1) = h(x) for all x ∈ X . The map f is then called a homotopy
between g and h. It is easy to see that homotopy is an equivalence relation, since a homotopy can
be “inverted” and two homotopies can be “concatenated”.
When g and h are two curves in Y = Rn defined over the same intervalX = [a, b], the homotopy
f defines, for each “time” t, 0 ≤ t ≤ 1, a curve f(·, t) : [a, b] → Rn that interpolates smoothly
between f(·, 0) = g and f(·, 1) = h.2
To define homotopy for two surfaces or more general spaces S and T , we start with the identity
map on S and deform it into a homeomorphism from S to T . Two topological subspaces S, T ⊆ X
are called homotopic if there is a continuous mapping
γ : S × [0, 1] → X
such that γ(·, 0) is the identity map on S and γ(·, 1) is a homeomorphism from S to T .
By the requirement that we have a homeomorphism at time t = 1, one can see that this
definition is symmetric in S and T . Note that we do not require γ(·, t) to be a homeomorphism
at all times t. Thus, a clockwise cycle and a counterclockwise cycle in the plane are homotopic.
In fact, all closed curves in the plane are homotopic: every cycle can be contracted into a point
(which is a special case of a closed curve). A connected topological space with this property is
called simply connected.
Examples of spaces which are not simply connected are a plane with a point removed, or a
(solid or hollow) torus. For example, on the hollow torus in Fig. 7.3, the closed curve in the figure
is not homotopic to its inverse.
If we require that γ(·, t) is a homeomorphism at all times during the deformation we arrive the
stronger concept of isotopy. For example, the smooth closed curves without self-intersections in the
plane fall into two isotopy classes, according to their orientation (clockwise or counterclockwise).
Isotopy is usually what is meant when speaking about a “topologically correct” approximation of
2In the case of curves with the same endpoints g(a) = h(a) and g(b) = h(b), one usually requires also that these
endpoints remain fixed during the deformation: f(a, t) = g(a) and f(b, t) = g(b) for all t.
7.3. SIMPLICIAL HOMOLOGY 5
a given surface, as discussed in Sect. 5.1, where the stronger concept of ambient isotopy is also
defined (Definition 1, p. 183).
A map f : X → Y is a homotopy equivalence if there is a map g : Y → X such that the composed
maps gf and fg are homotopy equivalent to the identity map (on X and Y , respectively). The
map g is a homotopy inverse of f . The spaces X and Y are called homotopy equivalent. A space
is contractible if it is homotopy equivalent to a point.
1. The unit ball in a Euclidean space is contractible. Let f : {0} → Bd be the inclusion map.
The constant map g : Bd → {0} is a homotopy inverse of f . To see this, observe that the
map fg is the identity, and gf is homotopic to the identity map on Bd, the homotopy being
the map F : Bd × [0, 1] → Bd defined by F (x, t) = tx.
2. The solid torus is homotopy equivalent to the circle. More generally, the cartesian product
of a topological space X and a contractible space is homotopy equivalent to X .
3. A punctured d-dimensional Euclidean space Rd \ {0} is homotopy equivalent to a (d − 1)-
sphere.
Note that homotopy equivalent spaces need not be homeomorphic. However, such spaces share
important topological properties, like having the same Betti numbers (to be introduced in the next
section). Section 6.2.3 (p. 250) describes how this concept is applied in surface reconstruction.
7.3 Simplicial homology
A calculus of closed loops. Intuitively, it is clear that the sphere and the torus have different
shapes in the sense that these surfaces are not homeomorphic. A formal proof of this observation
could be based on the Jordan curve theorem: take a simple closed curve on the torus that does
not disconnect the torus. Such curves, the complement of which is connected, do exist, as can be
seen from Fig. 7.3. If there exists a homeomorphism from the torus to the sphere, the image of the
curve on the torus would be a simple closed curve on the sphere. By the Jordan curve theorem,
the complement of this curve is disconnected. Since connectedness is preserved by homeomor-
phisms, the complements of the curves on the torus and the sphere are not homeomorphic. This
contradiction proves that the torus and the sphere are not homeomorphic.
Figure 7.3: Every simple closed curve on the sphere disconnects. Not every closed curve on the
torus disconnects.
This proof seems rather ad hoc: it only proves that the sphere is not homeomorphic to a
closed surface with holes, but it cannot be used to show that a surface with more than one hole
is not homeomorphic to the torus. Homology theory provides a systematic way to generalize the
argument above to more general spaces.
In this chapter we present basic concepts and properties of simplicial homology theory, closely
related to simplicial complexes and suitable for computational purposes. An alternative, more
6 CHAPTER 7. COMPUTATI