Topology for Computing (Cambridge Monographs on Applied and Computational Mathematics)
Afra J. Zomorodian
Language: English
Pages: 258
ISBN: 0521136091
Format: PDF / Kindle (mobi) / ePub
Written by a computer scientist for computer scientists, this book teaches topology from a computational point of view, and shows how to solve real problems that have topological aspects involving computers. Such problems arise in many areas, such as computer graphics, robotics, structural biology, and chemistry. The author starts from the basics of topology, assuming no prior exposure to the subject, and moves rapidly up to recent advances in the area, including topological persistence and hierarchical Morse complexes. Algorithms and data structures are presented when appropriate.
is that it is a special subset of the power set of all its vertices. The subset is special because of the requirements in Definition 2.32. Consider the small complex in Figure 2.11(a). The diagram (b) shows how the simplices connect within the complex: It has a node for each simplex and an 28 2 Spaces and Filtrations v -0.269616 0.228466 0.077226 v -0.358878 0.240631 0.044214 v -0.657287 0.527813 0.497524 v 0.186944 0.256855 0.318011 v -0.074047 0.212217 0.111664 ... f 19670 20463 20464 f 8936
view described in Section 6.1.5. Using this view, we extend and generalize the persistence algorithm to arbitrary dimensions and ground fields in Section 7.3. We do so by deriving the algorithm from the classic reduction scheme, illustrating that the algorithm derives its simple structure from the properties of the underlying algebraic structures. While no simple description exists over nonfields, we may still be interested in computing a single homology group over an arbitrary PID. We give an
operation is symmetric difference, as shown in Figure 7.1. The only nonzero Betti numbers to be computed are β0 , β1 , and β2 . We also need a filtration ordering of the simplices (Definition 2.44). We use 125 126 7 The Persistence Algorithms + Fig. 7.1. Symmetric difference in dimensions one and two. We add two 1-cycles to get a new 1-cycle. We add the surfaces that the cycles bound to get a spanning surface for the new 1-cycle. this total ordering to construct a filtration, where one, and
7.3.2 Derivation We use the small filtration in Figure 7.11 as a running example and compute over R, although any field will do. The persistence module corresponds to a R[t]-module by the correspondence established in Theorem 3.19. Table 7.1 reviews the degrees of the simplices of our filtration as homogeneous elements of this module. Throughout this section, we use {e j } and {eˆi } to represent homogeneous 140 7 The Persistence Algorithms Table 7.1. Degree of simplices of filtration in
Combinations allow us to represent regions of space with very few points. Definition 2.27 (combinations) Let S = {p0 , p1 , . . . , pk } ⊆ Rd . A linear combination is x = ∑ki=0 λi pi , for some λi ∈ R. An affine combination is a linear combination with ∑ki=0 λi = 1. A convex combination is a an affine combination with λi ≥ 0, for all i. The set of all convex combinations is the convex hull. Definition 2.28 (independence) A set S is linearly (affinely) independent if no point in S is a linear