Topology for Computing

Preface page xi
Acknowledgments xiii
1 Introduction 1
1.1 Spaces 1
1.2 Shapes of Spaces 3
1.3 New Results 8
1.4 Organization 10
Part One: Mathematics
2 Spaces andFiltrations 13
2.1 Topological Spaces 14
2.2 Manifolds 19
2.3 Simplicial Complexes 23
2.4 Alpha Shapes 32
2.5 Manifold Sweeps 37
3 Group Theory 41
3.1 Introduction to Groups 41
3.2 Characterizing Groups 47
3.3 Advanced Structures 53
4 Homology 60
4.1 Justification 60
4.2 Homology Groups 70
4.3 Arbitrary Coefficients 79
5 Morse Theory 83
5.1 Tangent Spaces 84
5.2 Derivatives and Morse Functions 85
5.3 CriticalPoints 86
5.4 Stable and Unstable Manifolds 88
5.5 Morse-Smale Complex 90
6 New Results 94
6.1 Persistence 95
6.2 Hierarchical Morse-Smale Complexes 105
6.3 Linking Number 116
Part Two: Algorithms
7 The Persistence Algorithms 125
7.1 Marking Algorithm 125
7.2 Algorithm for Z2 128
7.3 Algorithm for Fields 136
7.4 Algorithm for PIDs 146
8 Topological Simplification 148
8.1 Motivation 148
8.2 Reordering Algorithms 150
8.3 Conflicts 153
8.4 Topology Maps 157
9 The Morse-Smale Complex Algorithm 161
9.1 Motivation 162
9.2 The Quasi Morse-Smale Complex Algorithm 162
9.3 LocalT ransformations 166
9.4 Algorithm 169
10 The Linking Number Algorithm 171
10.1 Motivation 171
10.2 Algorithm 172
Part Three: Applications
11 Software 183
11.1 Methodology 183
11.2 Organization 184
11.3 Development 186
11.4 Data Structures 190
11.5 CView 193
12 Experiments 198
12.1 Three-DimensionalData 198
12.2 Algorithm for Z2 204
12.3 Algorithm for Fields 208
12.4 Topological Simplification 215
12.5 The Morse-Smale Complex Algorithm 217
12.6 The Linking Number Algorithm 220
13 Applications 223
13.1 ComputationalStructuralBiol ogy 223
13.2 Hierarchical Clustering 227
13.3 Denoising Density Functions 229
13.4 Surface Reconstruction 231
13.5 Shape Description 232
13.6 I/O Efficient Algorithms 233
Bibliography 235
Index 240
Color plates follow page 154