Efficient data structure for representing and simplifying simplicial complexes in high dimensions - AGPIG Accéder directement au contenu
Article Dans Une Revue International Journal of Computational Geometry and Applications Année : 2012

Efficient data structure for representing and simplifying simplicial complexes in high dimensions

Résumé

We study the simplification of simplicial complexes by repeated edge contractions. First, we extend to arbitrary simplicial complexes the statement that edges satisfying the {\em link condition} can be contracted while preserving the homotopy type. Our primary interest is to simplify {\em flag complexes} such as {\em Rips complexes} for which it was proved recently that they can provide topologically correct reconstructions of shapes. Flag complexes (sometimes called {\em clique complexes}) enjoy the nice property of being completely determined by the graph of their edges. But, as we simplify a flag complex by repeated edge contractions, the property that it is a flag complex is likely to be lost. Our second contribution is to propose a new representation for simplicial complexes particularly well adapted for complexes close to flag complexes. The idea is to encode a simplicial complex $K$ by the graph $G$ of its edges together with the inclusion-minimal simplices in the set difference $\Flag{G} \setminus K$. We call these minimal simplices {\em blockers}. We prove that the link condition translates nicely in terms of blockers and give formulae for updating our data structure after an edge contraction. Finally, we observe in some simple cases that few blockers appear during the simplification of Rips complexes, demonstrating the efficiency of our representation in this context.
Fichier principal
Vignette du fichier
2012-ijcga-Blockers.pdf (954.19 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00785082 , version 1 (05-02-2013)

Identifiants

Citer

Dominique Attali, André Lieutier, David Salinas. Efficient data structure for representing and simplifying simplicial complexes in high dimensions. International Journal of Computational Geometry and Applications, 2012, 22 (4), pp.279-303. ⟨10.1142/S0218195912600060⟩. ⟨hal-00785082⟩
244 Consultations
311 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More