A Computational Geometric Topology .............................. 1
I Graphs ....................................................... 3
1.1 Connected Components ....................................... 3
1.2 Curves in the Plane ........................................ 9
1.3 Knots and Links ........................................... 13
1.4 Planar Graphs ............................................. 18
Exercises ...................................................... 24
II Surfaces ................................................... 27
II.1 2-dimensional Manifolds ................................. 27
11.2 Searching a Triangulation ................................ 33
11.3 Self-intersections ....................................... 37
11.4 Surface Simplification ................................... 42
Exercises ...................................................... 47
III Complexes ................................................. 51
III.1 Simplicial Complexes .................................... 51
III.2 Convex Set Systems ...................................... 57
III.3 Delaunay Complexes ...................................... 63
III.4 Alpha Complexes ......................................... 68
Exercises ...................................................... 74
В Computational Algebraic Topology ............................ 77
IV Homology ................................................... 79
IV.1 Homology Groups .......................................... 79
IV.2 Matrix Reduction ......................................... 85
IV.3 Relative Homology ........................................ 90
IV.4 Exact Sequences .......................................... 95
Exercises ..................................................... 101
V Duality .................................................... 103
V.l Cohomology ............................................... 103
V.2 Poincare Duality ......................................... 108
V.3 Intersection Theory ...................................... 114
V.4 Alexander Duality ........................................ 118
Exercises ..................................................... 123
VI Morse Functions ........................................... 125
VI.l Generic Smooth Functions ................................ 125
VI.2 Transversality .......................................... 130
VI.3 Piecewise Linear Functions .............................. 135
VI.4 Reeb Graphs ............................................. 140
Exercises ..................................................... 145
С Computational Persistent Topology ......................... 147
VII Persistence .............................................. 149
VII.1 Persistent Homology .................................... 149
VII.2 Efficient Implementations .............................. 156
VII.3 Extended Persistence ................................... 161
VII.4 Spectral Sequences ..................................... 166
Exercises ..................................................... 171
VIII Stability ............................................... 175
VIII.l 1-parameter Families .................................. 175
VIII.2 Stability Theorems .................................... 180
VIII.3 Length of a Curve ..................................... 185
VIII.4 Bipartite Graph Matching .............................. 191
Exercises ..................................................... 197
IX Applications .............................................. 199
IX.1 Measures for Gene Expression Data ....................... 199
IX.2 Elevation for Protein Docking ........................... 206
IX.3 Persistence for Image Segmentation ...................... 213
IX.4 Homology for Root Architectures ......................... 218
Exercises ..................................................... 224
References .................................................... 227
Index ......................................................... 235
| 
