s'authentifier
version française rss feed

inria-00001187, version 1

Dynamic updates of succinct triangulations

Luca Castelli Aleardi 12, Olivier Devillers () 2, Gilles Schaeffer 1

18th Canadian Conference on Computational Geometry (2005)

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\lg m)$ bits are needed for representing triangulations of genus $g$ surfaces).

  • Domaine : Informatique/Géométrie algorithmique
    Informatique/Algorithme et structure de données
  • Commentaire : http://cs.uwindsor.ca/~cccg/
 
  • inria-00001187, version 1
  • oai:hal.inria.fr:inria-00001187
  • Contributeur : 
  • Soumis le : Mercredi 12 Avril 2006, 14:55:22
  • Dernière modification le : Jeudi 13 Avril 2006, 16:32:22
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...