2D Triangulation Representation Using Stable Catalogs

Olivier Devillers 1 Abdelkrim Mebarki 2 Luca Castelli Aleardi 1, 3
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée
2 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : The problem of representing triangulations has been widely studied to obtain convenient encodings and space efficient data structures. In this paper we propose a new practical approach to reduce the amount of space needed to represent in main memory an arbitrary triangulation, while maintaining constant time for some basic queries. This work focuses on the connectivity information of the triangulation, rather than the geometry information (vertex coordinates), since the combinatorial data represents the main storage part of the structure. The main idea is to gather triangles into patches, to reduce the number of pointers by eliminating the internal pointers in the patches and reducing the multiple references to vertices. To accomplish this, we define stable catalogs of patches that are close under basic standard update operations such as insertion and deletion of vertices, and edge flips. We present some bounds and results concerning special catalogs, and some experimental results for the quadrilateral-triangle catalog.
Type de document :
Communication dans un congrès
Proc. 18th Canadian Conference on Computational Geometry, Aug 2006, Kingston, Canada, France. 2006
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00090631
Contributeur : Olivier Devillers <>
Soumis le : vendredi 1 septembre 2006 - 11:09:21
Dernière modification le : jeudi 12 avril 2018 - 01:48:43
Document(s) archivé(s) le : mardi 6 avril 2010 - 00:43:40

Fichier

Identifiants

  • HAL Id : inria-00090631, version 1

Collections

Citation

Olivier Devillers, Abdelkrim Mebarki, Luca Castelli Aleardi. 2D Triangulation Representation Using Stable Catalogs. Proc. 18th Canadian Conference on Computational Geometry, Aug 2006, Kingston, Canada, France. 2006. 〈inria-00090631〉

Partager

Métriques

Consultations de la notice

370

Téléchargements de fichiers

170