s'authentifier
version française rss feed

inria-00070308, version 1

Dynamic updates of succinct triangulations

Luca Castelli Aleardi 1, Olivier Devillers () 1, Gilles Schaeffer a2

N° RR-5709 (2006)

Résumé : In a recent article, we presented a succinct representation of triangulations that supports efficient navigation operations. Here this representation is improved to allow for efficient local updates of the triangulations. Precisely, we show how a succinct representation of a triangulation with $m$ triangles can be maintained under vertex insertions in $O(1)$ amortized time and under vertex deletions/edge flips in $O(lg^2 m)$ amortized time. Our structure achieves the information theory bound for the storage for the class of triangulations with a boundary, requiring asymptotically $2.17m+o(m)$ bits, and supports adjacency queries between triangles in $O(1)$ time (an extra amount of $O(g lgm)$ bits are needed for representing triangulations of genus $g$ surfaces).

  • Domaine : Informatique/Autre
  • Mots-clés : GRAPH ENCODING – SUCCINCT DYNAMIC DATA STRUCTURES – TRIANGULATIONS – GEOMETRIC DATA STRUCTURES
  • Référence interne : RR-5709
 
  • inria-00070308, version 1
  • oai:hal.inria.fr:inria-00070308
  • Contributeur : 
  • Soumis le : Vendredi 19 Mai 2006, 20:00:06
  • Dernière modification le : Vendredi 3 Décembre 2010, 11:28:02
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...