COMPUTATIONAL TOPOLOGY - School of Mathematics

1 COMPUTATIONAL TOPOLOGYAN INTRODUCTIONH erbert Edelsbrunner and John HarerDepartments of Computer Science and MathematicsDuke UniversityTo our families and friendsTable of ContentsPart AIGraphs11 Connected Components22 Curves in the Plane93 Knots and Links154 Planar Graphs22 Exercises29 IISurfaces311 Two-dimensional Manifolds 322 Searching a Triangulation 393 Self-intersections454 Surface Simplification51 Exercises57 IIIC omplexes591 Simplicial Complexes602 Convex Set Systems673 Delaunay Complexes744 Alpha Complexes81 Exercises88 Part BIVH omology911 Homology Groups922 Matrix Reduction983 Relative Homology1044 Exact Sequences111 Exercises118 VDuality1211 Cohomology1222 Poincar e Duality1283 Intersection Theory1324 Alexander Duality136 Exercises139 VIMorse Functions1411 Generic Smooth Functions 1422 Transversality1483 Piecewise Linear Functions 1544 Reeb Graphs160 Exercises167 Part CVIIP ersistence1691 Persistent Homology1702 Efficient Implementations1783 Extended Persistence1844 Spectral Sequences191 Exercises198 VIIIS tability2011 Time Series2022 Stability Theorems2083 Length of a Curve2154 Bipartite Graph Matching221 Exercises228 IXApplications2311 Image

2 Segmentation2 Elevation3 Gene Expression4 Local Homology for Plant Root ArchitectureExercisesPart DXOpen Problems2371 Complexity of Reidemeister Moves2382 Shelling a 3-ball2393 Geometric Realization of 2-manifolds 2414 Embedding in Three Dimensions2425 Equipartion in Four Dimensions2436 Running-time of Matrix Reduction2447 Multi-parameter Persistence2458 Unfolding PL Critical Points2469 PL in the Limit24710 Counting Halving Sets248 Index259 PrefaceThe last ten years have witnessed that geometry, TOPOLOGY , and algorithmsform a potent mix of disciplines with many applications inside and outsideacademia.

3 We aim at bringing these developments to a larger audience. Thisbook has been written to be taught, and it is based on notes developed duringcourses delivered at Duke University and at the Berlin Mathematical School ,primarily to students of computer science and organizationinto chapters, sections, exercises, and open problems reflects the teaching stylewe practice. Each chapter develops a major topic and is worthabout twoweeks of teaching. The chapters are divided into sections, each a lecture ofone and a quarter hours. To convey a feeling for the boundary of the currentknowledge, we complement the material with descriptions ofopen interesting challenge is the mixed background of the audience.

4 How dowe teach TOPOLOGY to students with limited background in Mathematics , andhow do we convey algorithms to students with limited background in computerscience? Assuming no prior knowledge and appealing to the intelligence of thelistener is a good first step. Motivating the material by relating it to situationsin different walks of life is helpful in building up intuitionthat can cut throughotherwise necessary formalism. Exposing central ideas with simple means helpsand so does minimizing the necessary amount of material in this book is a combination of topics in geometry, TOPOLOGY ,and algorithms. Far from getting diluted, we find that the fields benefit fromeach other.

5 Geometry gives a concrete face to topological structures and al-gorithms offer a means to construct them at a level of complexity that passesthe threshold necessary for practical applications. As always, algorithms haveto be fast because time is the one fundamental resource humankind did notyet learn to manipulate for its selfish purposes. Beyond these obvious relation-ships, there is a symbiotic affinity between algorithms and the algebra used tocapture topological information. It is telling that both fields trace their nameback to the writing of the same Persian mathematician, al-Khwarizmi, work-ing in Baghdad during the ninth century after Christ.

6 Besides living in thetriangle spanned by geometry, TOPOLOGY , and algorithms, wefind it useful tocontemplate the place of the material in the tension betweenextremes such aslocal vs. global;discrete vs. continuous;abstract vs. concrete;intrinsic vs. insights are often obtained by a meaningful integration of local infor-mation. This is how we proceed in many fields, taking on biggerchallengesafter mastering the small. But small things are big from up close and big onessmall from afar. Indeed, the question of scale lurking behind this thought isthe driving force for much of the development described in this book.

7 Thedichotomy between discrete and continuous structures is driven by opposinggoals, machine computation and human understanding. Both are illusions thatare useful to have but should not be confused with anything intangible likereality. The tension between the abstract and the concrete as well as betweenthe intrinsic and the extrinsic have everything to do with human approach toknowledge. An example close to home is the step from geometryto topologyin which we remove the burdens of size to focus on the phenomenon of con-nectivity. The more abstract the context the more general the insight. Now,generality is good but it is not a substitute for the concretesteps that haveto be taken to build bridges to applications.

8 Zooming in and out of generalityleads to unifying viewpoints and suggests meaningful integrations where these thoughts have certainly influenced us in the selection of the ma-terial and in its presentation, there is a long way to the concrete instantiationwe call this book. The hardest part is to land, and we do in fourparts decom-posed into a total of ten chapters. Part A is a gentle introduction to topologicalthought. Discussing Graphs in Chapter I, Surfaces in Chapter II, and Com-plexes in Chapter III, we gradually build up topological sophistication, alwaysin combination with geometric and algorithmic ideas.

9 Part Bpresents classicalmaterial from TOPOLOGY . We focus on what we deem useful and efficiently com-putable. The material on Homology in Chapter IV and on Duality in ChapterV is exclusively algebraic. In the discussion of Morse Theory in Chapter VI,we build a bridge to differential concepts in TOPOLOGY . Part Cis mostly noveland indeed the main reason we write this book. The main new concept isPersistence introduced in Chapter VII and its Stability discussed in ChapterVIII. Finally, we address connections to Singularities in Chapter IX. Part Dconcludes the book with a small collection of open problems in computationaltopology.

10 It is our hope that they point in the right direction, leading a newgeneration of researchers far and beyond what we currently a project like writing this book there are many who contribute, directlyor indirectly. We want to thank all and we don t know where to begin. Aboveall, we thank our colleagues in academia and industry, our students, and ourpostdoctoral fellows for their ideas, criticism, and encouragement. And mostof all for the sense of purpose they provide. We thank Duke University forproviding the facilities and intellectual environment that allowed us to engagein the line of research leading to this book.