Simplicial sets and cubical sets are combinatorial structures which have been studied for a long time in Algebraic Topology. These structures describe sets of regular cells, respectively simplices ...and cubes, and any kind of assembly of cells can be represented. They are used for many applications in Computational Topology, Geometric Modeling, CAD/CAM, Computer Graphics, etc. For instance, simplicial and cubical sets are ”naturally” associated with simplicial and cubical Bézier spaces.
In this paper, a new combinatorial structure, namely simploidal sets is defined for representing and handling Bézier simploids. Simploidal sets describe sets of simploids, which are also regular cells corresponding to Cartesian product of simplices. Simplices and cubes are then particular simploids.
In order to associate shapes with structures, structural relations between simploidal sets and simploidal Bézier spaces are also stated. In fact, simploidal sets generalize and homogenize simplicial and cubical sets.
Construction operations are also defined, extending all those of simplicial and cubical sets: cone, Cartesian product, degeneracy, and identification. In their basic version, the first three operations allow to create any simploid, and the last one, to create any assembly of simploids. It is then possible to simultaneously handle through a single formalism any assembly of simplices, cubes, and other simploids, with a very low additional cost, regarding space (data structure), time (construction or computation operations) or software development.
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 book constitutes the refereed proceedings of the 12th International Conference on Discrete Geometry for Computer Imagery, DGCI 2005, held in Poitiers, France in April 2005.
The 36 revised full ...papers presented together with an invited paper were carefully reviewed and selected from 53 submissions. The papers are organized in topical sections on applications, discrete hierarchical geometry, discrete tomography, discrete topology, object properties, reconstruction and recognition, uncertain geometry, and visualization.
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.
The combinatorial structure of simploidal sets generalizes both simplicial complexes and cubical complexes. More precisely, cells of simploidal sets are cartesian product of simplices. This structure ...can be useful for geometric modeling (e.g. for handling hybrid meshes) or image analysis (e.g. for computing topological properties of parts of
n
-dimensional images). In this paper, definitions and basic constructions are detailed. The homology of simploidal sets is defined and it is shown to be equivalent to the classical homology. It is also shown that products of Bézier simplicial patches are well suited for the embedding of simploidal sets.
Graph pyramids are often used for representing irregular image pyramids. For the 2D case, combinatorial pyramids have been recently defined in order to explicitly represent more topological ...information than graph pyramids. The main contribution of this work is the definition of pyramids of $n$-dimensional generalized maps. This extends the previous works to any dimension, and generalizes them in order to represent any type of pyramid built by using any removal and/or contraction operations. We give basic algorithms that allow to build an n-dimensional generalized pyramid that describes a multi-level segmented image. A pyramid of n-dimensional generalized maps can be implemented in several ways. We propose three possible representations and give conversion algorithms.
In this paper, we show how to use the three dimensional topological map in order to compute efficiently topological features on objects contained in a 3D image. These features are useful for example ...in image processing to control operations or in computer vision to characterize objects. Topological map is a combinatorial model which represents both topological and geometrical information of a three dimensional labeled image. This model can be computed incrementally by using only two basic operations: the removal and the fictive edge shifting. In this work, we show that Euler characteristic can be computed incrementally during the topological map construction. This involves an efficient algorithm and open interesting perspectives for other features.
PDF
