Explicit array-based compact data structures for triangulations

Luca Castelli Aleardi 1 Olivier Devillers 2
2 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : We consider the problem of designing space efficient solutions for representing triangle meshes. Our main result is a new explicit data structure for compactly representing planar triangulations: if one is allowed to permute input vertices, then a triangulation with n vertices requires at most 4n references (5n references if vertex permutations are not allowed). Our solution combines existing techniques from mesh encoding with a novel use of minimal Schnyder woods. Our approach extends to higher genus triangulations and could be applied to other families of meshes (such as quadrangular or polygonal meshes). As far as we know, our solution provides the most parsimonious data structures for triangulations, allowing constant time navigation in the worst case. Our data structures require linear construction time, and all space bounds hold in the worst case. We have implemented and tested our results, and experiments confirm the practical interest of compact data structures.
Type de document :
Communication dans un congrès
Takao Asano and Shin-ichi Nakano and Yoshio Okamoto and Osamu Watanabe. 22nd International Symposium on Algorithms and Computation, 2011, Yokohama, Japan. Springer-Verlag, 7074, pp.312--322, 2011, LNCS
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger


https://hal.inria.fr/hal-00678615
Contributeur : Olivier Devillers <>
Soumis le : mardi 13 mars 2012 - 14:20:44
Dernière modification le : jeudi 11 janvier 2018 - 16:25:56
Document(s) archivé(s) le : jeudi 14 juin 2012 - 17:54:51

Fichiers

CompactTriangleMeshes.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00678615, version 1

Collections

Citation

Luca Castelli Aleardi, Olivier Devillers. Explicit array-based compact data structures for triangulations. Takao Asano and Shin-ichi Nakano and Yoshio Okamoto and Osamu Watanabe. 22nd International Symposium on Algorithms and Computation, 2011, Yokohama, Japan. Springer-Verlag, 7074, pp.312--322, 2011, LNCS. 〈hal-00678615〉

Partager

Métriques

Consultations de la notice

465

Téléchargements de fichiers

402