Array-based Compact Data Structures for Triangulations: Practical Solutions with Theoretical Guarantees

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 maximal Schnyder woods. Our approach could be extended to deal with higher genus triangulations and 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. Our data structures require linear construction time, and are fast decodable from a compressed format without using additional memory allocation. All bounds, concerning storage requirements and navigation performance, 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 :
Article dans une revue
Journal of Computational Geometry, Carleton University, Computational Geometry Laboratory, 2018, 9 (1), pp.247-289. 〈10.20382/jocg.v9i1a8〉
Liste complète des métadonnées

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


https://hal.inria.fr/hal-01846652
Contributeur : Olivier Devillers <>
Soumis le : dimanche 22 juillet 2018 - 16:34:23
Dernière modification le : mercredi 25 juillet 2018 - 01:15:29

Fichiers

332-1546-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Luca Castelli Aleardi, Olivier Devillers. Array-based Compact Data Structures for Triangulations: Practical Solutions with Theoretical Guarantees. Journal of Computational Geometry, Carleton University, Computational Geometry Laboratory, 2018, 9 (1), pp.247-289. 〈10.20382/jocg.v9i1a8〉. 〈hal-01846652〉

Partager

Métriques

Consultations de la notice

112

Téléchargements de fichiers

36