Computational Topology: An Introduction

Over the last ten years a field called “computational topology” has developed from a potent mix of geometry, topology and algorithms. The ideas have been percolating through the engineering and biology literature, and whole conferences have been dedicated to specific applications. For systems like wireless networks, for example, there are homological criteria for sensor coverage and identification of coverage gaps. This book offers an introduction to the subject that is aimed at emerging applications in biology. It is similar in scope and spirit to Zomorodian’s Topology for Computing.

The approach is designed for advanced undergraduates and beginning graduate students of mathematics and computer science. The authors recognize that, in many cases, they need to teach topology to students with limited mathematical backgrounds and algorithmic thinking to students inexperienced with computer science and data structures. The intriguing combination of geometry, topology and algorithms gives the subject a concreteness that may appeal to many students.

The first two-thirds of the book focuses on geometric and algebraic topology viewed from a computational perspective. The topics are mostly standard, but the treatment is not. While many theorems are stated, there are very few proofs. The emphasis instead is informational and utilitarian: what the theorems mean, and how they support development of algorithms. It is fascinating, if slightly weird, to see exact sequences on one page and computer pseudo-code a few pages later.

The basic topology is taught in six chapters called Graphs, Surfaces, Complexes, Homology, Duality and Morse Functions. The pace is fast: all this topology is covered in less than 150 pages. The last three chapters are more specialized; they focus on the concepts of persistence and stability and their applications.

Persistence is a measure-theoretic concept overlaid on algebraic structures. The idea of persistence is driven by a practical need to cope with noise in data. The key tool is persistent homology, which can be used to measure the scale or resolution of a topological feature. This has two parts — a geometric part that defines a function on a topological space, and an algebraic part that turns the function into measurements. The most important property of persistence is its stability under perturbations of the data.

The four case studies treated in the last chapter illustrate the application of persistence in biology: to gene expression data, protein docking, segmentation of images from various imaging systems, and homology of plant root architectures.

Each chapter has a small collection of exercises; an instructor would probably need to supplement these. The bibliography is substantial.

Bill Satzer (wjsatzer@mmm.com) is a senior intellectual property scientist at 3M Company, having previously been a lab manager at 3M for composites and electromagnetic materials. His training is in dynamical systems and particularly celestial mechanics; his current interests are broadly in applied mathematics and the teaching of mathematics.