Computational Topology An Introduction

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