Contents
Preface xi
A Computational Geometric Topology 1
I Graphs 3
I.1 Connected Components . . . . . . . . . . . . . . . . . . . . . . . 3
I.2 Curves in the Plane . . . . . . . . . . . . . . . . . . . . . . . . . 9
I.3 Knots and Links . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
I.4 Planar Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
II Surfaces 27
II.1 2-dimensional Manifolds . . . . . . . . . . . . . . . . . . . . . . 27
II.2 Searching a Triangulation . . . . . . . . . . . . . . . . . . . . . . 33
II.3 Self-intersections . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
II.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
vii
Previous Page Next Page