Skip to Main content Skip to Navigation

Calcul incrémental des groupes d'homologie d'un objet au cours d'un processus de construction

Abstract : Topology-based geometric modeling involves objects subdivided into cells of various dimensions (vertices, edges, faces, volumes...). Computing topological invariants (orientability, contractibility, Euler characteristic...) helps to characterize the structure of these objects. Especially, homology is a topological invariant usually studied to characterize the holes of an object in any dimension (connected components in dimension 0, tunnels in dimension 1, cavities in dimension 2 etc. . .).Classically, computing the homology of an object requires to study the incidence relationships between all of its cells. In this thesis, we’re interested in computing incrementally the homology variations of an object evolving during a construction process. To achieve this goal, we are using effective homology results [1], and more specifically the effective short exact sequences theorem (SES theorem).Progressing from a construction step to an other is done by applying a local operation on the object and consists either in merging cells (identification) or in splitting cells (desidentification). The SES theorem is used to maintain a homological equivalence over the construction process. It relates the object to a smaller one having "the same" homology. At each step, homology is computed using this small object rather than the object itself, so that the computation is more efficient.In this context, we analyze the computational costs implied by the SES theorem. We observe that, in order to compute homology ranks at each step, the time complexity to maintain a homological equivalence depends on the amount of cells that the operation impacts (and their star), and the space complexity between two steps also grows accordingly. To ensure these results in practice, we highlight some prerequisites that an implementation has to fulfill. We provide a data structure that can be used for this purpose. It consists in maintaining some data in order to track the evolution of the cells of a topological structure over the construction process, that is the fact that some cells may die or be created. Depending on these evolutions, it is used to update every elements maintained over the construction process and used by the SES theorem, such as the boundary matrices of chain complexes.Next, we suppose that the object is too bulky to be manipulated by a single computation unit. We propose an algorithm to compute the homology of a distributed object evolving during a construction process made up only of identifications. The object is implicitly represented through its distribution and an identification describing a way to reconstruct it from its distribution. At each step, when an identification is applied on the object, these data are updated so that, at the next step, homology can be computed without reconstructing the object.At last, we provide a common framework between effective homology and persistent homology. More precisely, we look into the works dealing with towers, which are sequences of simplicial complexes linked to one another through simplicial maps [2].[1] Julio Rubio and Francis Sergeraert. Constructive homological algebra and applications.Technical report, Universidad de la Rioja, Université Grenoble Alpes, 2006[2] Tamal K Dey, Fengtao Fan, and Yusu Wang. Computing topological persistence forsimplicial maps. In Proceedings of the thirtieth annual symposium on Computational geometry,pages 345–354, 2014
Complete list of metadata
Contributor : ABES STAR :  Contact
Submitted on : Monday, June 27, 2022 - 2:03:15 PM
Last modification on : Tuesday, June 28, 2022 - 3:12:50 AM


Version validated by the jury (STAR)


  • HAL Id : tel-03706051, version 1



Wassim Rharbaoui. Calcul incrémental des groupes d'homologie d'un objet au cours d'un processus de construction. Géométrie algorithmique [cs.CG]. Université de Poitiers, 2022. Français. ⟨NNT : 2022POIT2253⟩. ⟨tel-03706051⟩



Record views


Files downloads