Explicit array-based compact data structures for triangulations: practical solutions with theoretical guarantees

Résumé : Nous nous intéressons là la conception de représentations efficaces pour les maillages triangulaires. Le résultat principal de ce travail est une nouvelle structure de données pour la représentation compacte des triangulations planaires: si on autorise la permutation des sommets du maillages, alors une triangulations à n sommets peut se représenter avec au plus 4n références (5n références sont nécessaires, si on ne fait pas de permutation). Notre solution combine des techniques existantes de codage de graphes avec une nouvelle utilisation des Schnyder woods minimaux. Cette approche s'étend aussi au cas de triangulations de genre supérieur et pourrait s'appliquer à d'autres familles de maillages (tels que les maillages quadrangulaires ou polygonaux). A notre connaissance, ce résultat fournit la structure de données la plus compacte pour les triangulations, permettant la navigation dans le maillage en temps constant dans le pire des cas. Le temps de construction de nos représentations est linéaire, et toutes les bornes sont valables dans le pire des cas. Nous avons implémenté et testé nos résultats, et nos expériences confirment l'intérêt pratique des structures de données compactes.
Type de document :
Rapport
[Research Report] RR-7736, INRIA. 2017, pp.39
Liste complète des métadonnées

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


https://hal.inria.fr/inria-00623762
Contributeur : Olivier Devillers <>
Soumis le : jeudi 23 novembre 2017 - 17:47:28
Dernière modification le : jeudi 10 mai 2018 - 02:06:32

Fichiers

RR-7736v2.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00623762, version 3

Citation

Luca Castelli Aleardi, Olivier Devillers. Explicit array-based compact data structures for triangulations: practical solutions with theoretical guarantees. [Research Report] RR-7736, INRIA. 2017, pp.39. 〈inria-00623762v3〉

Partager

Métriques

Consultations de la notice

666

Téléchargements de fichiers

83