Algebraic Topology and Topology Invariants - Mathematical Tools for Shape Analysis and Description - page 59

Euler characteristics [ 93 ]. Unfortunately these generators are not optimal (in the sense of the
shortest length) and in some cases the total number of edges of a single generator is O.n/ [ 58 ,
203 ].
Figure 7.6: Homologous cycles of a set of models, the optimal cycles extracted by [ 59 ] are in green.
In general, computing the optimal homologous cycles under Z 2 coefficients is NP-hard.
e solution proposed in [ 59 ] is to switch to the coefficient group Z . In that case, the problem of
finding optimal cycles in a given homology class is reduced to an optimization problem, which is
inherently an integer programming problem that can be solved in polynomial time. One conse-
quence of this result is that it is possible to compute in polynomial time an optimal 2-cycle in a
given homology class for any finite simplicial complex embedded in R 3 . Figure 7.6 depicts in red
a set of homologous cycles and in green the optimal cycles obtained with the method [ 59 ].
e direct application of the homologous generators is to use them as the cuts to flatten a
shape into a disk [ 75 ] and, in general, to parametrize it [ 93 ]. Recent advances on the approxi-
mation of loops in a computationally efficient way take advantage of topological persistence [ 60 ]
and Reeb graphs [ 57 ], topics that are described in chapters 9 and 11 .