Fast, Simple and Separable Computation of Betti Numbers on Three-dimensional Cubical Complexes - Archive ouverte HAL Access content directly
Conference Papers Year : 2016

Fast, Simple and Separable Computation of Betti Numbers on Three-dimensional Cubical Complexes

(1, 2) , (3) , (1) , (1) , (2)
1
2
3
Alexandra Bac
Jean-Luc Mari

Abstract

Betti numbers are topological invariants that count the number of holes of each dimension in a space. Cubical complexes are a class of CW complex whose cells are cubes of different dimensions such as points, segments, squares, cubes, etc. They are particularly useful for modeling structured data such as binary volumes. We introduce a fast and simple method for computing the Betti numbers of a three-dimensional cubical complex that takes advantage on its regular structure, which is not possible with other types of CW complexes such as simplicial or polyhedral complexes. This algorithm is also restricted to three-dimensional spaces since it exploits the Euler-Poincaré formula and the Alexander duality in order to avoid any matrix manipulation. The method runs in linear time on a single core CPU. Moreover, the regular cubical structure allows us to obtain an efficient implementation for a multi-core architecture.
Fichier principal
Vignette du fichier
CTIC2016.compressed.pdf (424.93 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-01341014 , version 1 (23-02-2017)

Identifiers

Cite

Aldo Gonzalez-Lorenzo, Mateusz Juda, Alexandra Bac, Jean-Luc Mari, Pedro Real. Fast, Simple and Separable Computation of Betti Numbers on Three-dimensional Cubical Complexes. 6th International Workshop on Computational Topology in Image Context (CTIC 2016), Jun 2016, Marseille, France. pp.130-139, ⟨10.1007/978-3-319-39441-1_12⟩. ⟨hal-01341014⟩
145 View
1506 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More