This paper deals with the homology computation of a subdivided object during its construction. In this paper, we focus on the construction operation consisting of merging cells. For each step of the ...construction, a homological equivalence is maintained. This algebraic structure connects the chain complex associated with the object to a smaller object (i.e. containing less cells) having the same homology. So, homology computation is achieved on this smaller object more efficiently than on the constructed object, due to their respective sizes. We prove that, at each step, maintaining the homological equivalence has a complexity depending only on the size of the part of the object impacted by the operation. We define a convenient data structure based on sparse matrices that guarantees this result in practice, and show some experimental results obtained with its implementation. Moreover, the method may also be used to compute homology groups generators of any dimension at the cost of an increased complexity.
•Application of the Short Exact Sequence theorem in the case of an identification.•Tracking the variations of homology of an object evolving over a construction process.•Homology groups computation, including torsion and generators of any dimension.•Computation with a theoretical complexity depending on the number of identified cells.•Conception and implementation of a data structure ensuring the theoretical complexity.
This paper focuses on homology computation over ‘cellular’ structures that allow multi-incidence between cells. We deal here with combinatorial maps, more precisely chains of maps and subclasses such ...as maps and generalized maps. Homology computation on such structures is usually achieved by computing simplicial homology on a simplicial analog. But such an approach is computationally expensive because it requires computing this simplicial analog and performing the homology computation on a structure containing many more cells (simplices) than the initial one. Our work aims at providing a way to compute homologies directly on a cellular structure. This is done through the computation of incidence numbers. Roughly speaking, if two cells are incident, then their incidence number characterizes how they are attached. Having these numbers naturally leads to the definition of a boundary operator, which induces a homology. Hence, we propose a boundary operator for chains of maps and provide optimization for maps and generalized maps. It is proved that, under specific conditions, the homology of a combinatorial map as defined in the paper is equivalent to the homology of its simplicial analogue.
This paper shows that a well-known algorithm proposed to compute the canonical polygonal schema of a surface can be transferred onto a 2-dimensional generalized map. We show that transformation rules ...on polygonal schemata can be achieved in O(1) with generalized maps, which can help optimizing existing algorithms.
Many combinatorial structures have been designed to represent the topology of space subdivisions and images. We focus here on two particular models, namely the
n
-
G
-maps used in geometric modeling ...and computational geometry and the
n
-surfaces used in discrete imagery. We show that a subclass of
n
-
G
-maps is equivalent to
n
-surfaces. To achieve this, we provide several characterizations of
n
-surfaces. Finally, the proofs being constructive, we show how to switch from one representation to another effectively.
Border Operator for Generalized Maps Alayrangues, Sylvie; Peltier, Samuel; Damiand, Guillaume ...
Discrete Geometry for Computer Imagery
Book Chapter, Conference Proceeding
Recenzirano
Odprti dostop
In this paper, we define a border operator for generalized maps, a data structure for representing cellular quasi-manifolds. The interest of this work lies in the optimization of homology ...computation, by using a model with less cells than models in which cells are regular ones as tetrahedra and cubes. For instance, generalized maps have been used for representing segmented images. We first define a face operator to retrieve the faces of any cell, then deduce the border operator and prove that it satisfies the required property : border of border is void. At last, we study the links between the cellular homology defined from our border operator and the classical simplicial homology.
Topological invariants are extremely useful in many applications related to digital imaging and geometric modeling, and homology is a classical one, which has not yet been fully explored in image ...applications. We present an algorithm that computes the whole homology of an object of arbitrary dimension: Betti numbers, torsion coefficients and generators. Effective implementation of this algorithm has been realized in order to perform experimentations. Results on classical shapes in algebraic topology and on discrete objects are presented and discussed.
Computation of Homology Groups and Generators Peltier, Samuel; Alayrangues, Sylvie; Fuchs, Laurent ...
Discrete Geometry for Computer Imagery,
2005
Book Chapter, Conference Proceeding
Recenzirano
Odprti dostop
Topological invariants are extremely useful in many applications related to digital imaging and geometric modelling, and homology is a classical one. We present an algorithm that computes the whole ...homology of an object of arbitrary dimension: Betti numbers, torsion coefficients and generators. Results on classical shapes in algebraic topology are presented and discussed.
Many combinatorial structures have been designed to represent the topology of space subdivisions and images. We focus here on two particular models, namely the n-G-maps used in geometric modeling and ...computational geometry and the n-surfaces used in discrete imagery. We show that a subclass of n-G-maps is equivalent to n-surfaces. We exhibit a local property characterising this subclass, which is easy to check algorithmatically. Finally, the proofs being constructive, we show how to switch from one representation to another effectively.
PDF
