55,844 research outputs found
Efficient computation of simplicial homology through acyclic matching
No full textWe consider the problem of efficiently computing homology with Z coefficients as well as homology generators for simplicial complexes of arbitrary dimension. We analyze, compare and discuss the equivalence of different methods based on combining reductions, co reductions and discrete Morse theory. We show that the combination of these methods produces theoretically sound approaches which are mutually equivalent. One of these methods has been implemented for simplicial complexes by using a compact data structure for representing the complex and a compact encoding of the discrete Morse gradient. We present experimental results and discuss further developments
Computing discrete Morse complexes from simplicial complexes
No full textWe consider the problem of efficiently computing a discrete Morse complex on simplicial complexes of arbitrary dimension and very large size. Based on a common graph-based formalism, we analyze existing data structures for simplicial complexes, and we define an efficient encoding for the discrete Morse gradient on the most compact of such representations. We theoretically compare methods based on reductions and coreductions for computing a discrete Morse gradient, proving that the combination of reductions and coreductions produces new mutually equivalent approaches. We design and implement a new algorithm for computing a discrete Morse complex on simplicial complexes. We show that our approach scales very well with the size and the dimension of the simplicial complex also through comparisons with the only existing public-domain algorithm for discrete Morse complex computation. We discuss applications to the computation of multi-parameter persistent homology and of extremum graphs for visualization of time-varying 3D scalar fields
Topologically-consistent simplification of discrete Morse complex
No full textWe address the problem of simplifying Morse–Smale complexes computed on volume datasets based on discrete Morse theory. Two approaches have been proposed in the literature based on a graph representation of the Morse–Smale complex (explicit approach) and on the encoding of the discrete Morse gradient (implicit approach). It has been shown that this latter can generate topologically-inconsistent representations of the Morse–Smale complex with respect to those computed through the explicit approach. We propose a new simplification algorithm that creates topologically-consistent Morse–Smale complexes and works both with the explicit and the implicit representations. We prove the correctness of our simplification approach, implement it on volume data sets described as unstructured tetrahedral meshes and evaluate its simplification power with respect to the usual Morse simplification algorithm
Clique Community Persistence: A Topological Visual Analysis Approach for Complex Networks
No full textTopological modifications and hierarchical representation of cell complexes in arbitrary dimensions
No full textWe propose a set of atomic modeling operators for simplifying and refining cell complexes in arbitrarydimensions. Such operators either preserve the homology of the cell complex, or they modify it in a con-trolled way. We show that such operators form a minimally complete basis for updating cell complexes,and we compare them with various operators previously proposed in the literature. Based on the newoperators, we define a hierarchical model for cell complexes, that we call aHierarchical Cell Complex(HCC), and we discuss its properties. AnHCCimplicitly encodes a virtually continuous set of complexesobtained from the original complex through the application of our operators. Then, we describe theimplementation of a version of theHCCbased on the subset of the proposed modeling operators whichpreserve homology. We apply the homology-preservingHCCto enhance the efficiency in extractinghomology generators at different resolutions. To this aim, we propose an algorithm which computeshomology generators on the coarsest representation of the original complex, and uses the hierarchicalmodel to propagate them to complexes at any intermediate resolution, and we prove its correctness.Finally, we present experimental results showing the efficiency and effectiveness of the proposedapproac
Persistent homology: A step-by-step introduction for newcomers
No full textPersistent homology is a powerful notion rooted in topological data analysis which allows for retrieving the essential topological features of an object. The attention on persistent homology is constantly growing in a large number of application domains, such as biology and chemistry, astrophysics, automatic classification of images, sensor and social network analysis. Thus, an increasing number of researchers is now approaching to persistent homology as a tool to be used in their research activity. At the same time, the literature lacks of tools for introducing beginners to this topic, especially if they do not have a strong mathematical background in algebraic topology. We propose here two complementary tools which meet this requirement. The first one is a web-based user-guide equipped with interactive examples to facilitate the comprehension of the notions at the basis of persistent homology. The second one is an interactive tool, with a specific focus on shape analysis, developed for studying persistence pairs by visualizing them directly on the input complex
Morse complexes for shape segmentation and homological analysis: discrete models and algorithms
No full textMorse theory offers a natural and mathematically-sound tool for shape analysis and understanding. It allows
studying the behavior of a scalar function defined on a manifold. Starting from a Morse function, we can decompose the domain of the function into meaningful regions associated with the critical points of the function. Such
decompositions, called Morse complexes, provide a segmentation of a shape and are extensively used in terrain
modeling and in scientific visualization. Discrete Morse theory, a combinatorial counterpart of smooth Morse
theory defined over cell complexes, provides an excellent basis for computing Morse complexes in a robust and
efficient way. Moreover, since a discrete Morse complex computed over a given complex has the same homology
as the original one, but fewer cells, discrete Morse theory is a fundamental tool for efficiently detecting holes
in shapes through homology and persistent homology. In this survey, we review, classify and analyze algorithms
for computing and simplifying Morse complexes in the context of such applications with an emphasis on discrete
Morse theory and on algorithms based on i
- …
