Abstract
We introduce here a new \(\mathbb{F}_2\) homology computation algorithm based on a generalization of the spanning tree technique on a finite 3-dimensional cell complex K embedded in ℝ3. We demonstrate that the complexity of this algorithm is linear in the number of cells. In fact, this process computes an algebraic map φ over K, called homology gradient vector field (HGVF), from which it is possible to infer in a straightforward manner homological information like Euler characteristic, relative homology groups, representative cycles for homology generators, topological skeletons, Reeb graphs, cohomology algebra, higher (co)homology operations, etc. This process can be generalized to others coefficients, including the integers, and to higher dimension.
This work has been partially supported by PAICYT research project FQM-296, “Andalusian research project” PO6-TIC-02268, Spanish MEC project MTM2006-03722 and the Austrian Science Fund under grant P20134-N13.
Chapter PDF
Similar content being viewed by others
References
Birkhoff, G.: Lattice Theory. American Mathematical Society, Providence (1948)
Delfinado, C.J.A., Edelsbrunner, H.: An incremental algorithm for betti numbers of simplicial complexes on the 3–sphere. Comput. Aided Geom. Design 12, 771–784 (1995)
González-Diaz, R., Jiménez, M.J., Medrano, B., Molina-Abril, H., Real, P.: Integral operators for computing homology generators at any dimension. In: Ruiz-Shulcloper, J., Kropatsch, W.G. (eds.) CIARP 2008. LNCS, vol. 5197, pp. 356–363. Springer, Heidelberg (2008)
Madjid, A., Corriveau, D., Ziou, D.: Morse homology descriptor for shape characterization. In: ICPR 2004: Proceedings of the Pattern Recognition, 17th International Conference on (ICPR 2004), Washington, DC, USA, vol. 4, pp. 27–30. IEEE Computer Society, Los Alamitos (2004)
Molina-Abril, H., Real, P.: Advanced homological information on 3d digital volumes. In: da Vitoria Lobo, N., Kasparis, T., Roli, F., Kwok, J.T., Georgiopoulos, M., Anagnostopoulos, G.C., Loog, M. (eds.) SSSPR 2008. LNCS, vol. 5342, pp. 361–371. Springer, Heidelberg (2008)
Molina-Abril, H., Real, P.: Cell at-models for digital volumes. In: 7th IAPR -TC-15 Workshop on Graph-based Representations in Pattern Recognition, Venice (Italy). LNCS, Springer, Heidelberg (2009)
Molina-Abril, H., Real, P.: Homological tree-based strategies for image analysis. In: Jiang, X., Petkov, N. (eds.) CAIP 2009. LNCS, vol. 5702, pp. 326–333. Springer, Heidelberg (2009)
Mrozek, M., Pilarczykand, P., Zelazna, N.: Homology algorithm based on acyclic subspace. Computers and Mathematics with Applications 55, 2395–2412 (2008)
Munkres, J.: Elements of Algebraic Topology. Addison Wesley Co., Reading (1984)
Peltier, S., Ion, A., Kropatsch, W.G., Damiand, G., Haxhimusa, Y.: Directly computing the generators of image homology using graph pyramids. Image Vision Comput. 27(7), 846–853 (2009)
Scopigno, R., Zorin, D., Carlsson, G., Zomorodian, A., Collins, A., Guibas, L.: Persistence barcodes for shapes (2004)
Storjohann, A.: Near optimal algorithms for computing smith normal forms of integer matrices, pp. 267–274 (1996)
Tarjan, R.: Finding dominators in directed graphs. SIAM J. on Comput. 3, 62–89 (1974)
Zelawski, M.: Pattern recognition based on homology theory. MG&V 14(3), 309–324 (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Molina-Abril, H., Real, P. (2009). Homological Computation Using Spanning Trees. In: Bayro-Corrochano, E., Eklundh, JO. (eds) Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications. CIARP 2009. Lecture Notes in Computer Science, vol 5856. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-10268-4_32
Download citation
DOI: https://doi.org/10.1007/978-3-642-10268-4_32
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-10267-7
Online ISBN: 978-3-642-10268-4
eBook Packages: Computer ScienceComputer Science (R0)