s'authentifier
version française rss feed

inria-00090707, version 1

Succinct representation of triangulations with a boundary

Luca Castelli Aleardi 12, Olivier Devillers () a2, Gilles Schaeffer b1

9th Workshop on Algorithms and Data Structures 3608 (2005) 134--135

Résumé : We consider the problem of designing succinct geometric data structures while maintaining efficient navigation operations. A data structure is said succinct if the asymptotic amount of space it uses matches the entropy of the class of structures represented. For the case of planar triangulations with a boundary we propose a succinct representation of the combinatorial information that improves to 2.175 bits per triangle the asymptotic amount of space required and that supports the navigation between adjacent triangles in constant time (as well as other standard operations). For triangulations with $m$ faces of a surface with genus g, our representation requires asymptotically an extra amount of 36(g-1)lg m bits (which is negligible as long as g << m/lg m).

  • Domaine : Informatique/Géométrie algorithmique
 
  • inria-00090707, version 1
  • oai:hal.inria.fr:inria-00090707
  • Contributeur : 
  • Soumis le : Vendredi 1 Septembre 2006, 15:06:16
  • Dernière modification le : Vendredi 1 Septembre 2006, 15:28:44
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...