Catalog Based Representation of 2D triangulations

Abstract : Several Representations and Coding schemes have been proposed to represent efficiently 2D triangulations. In this paper we propose a new practical approach to reduce the main memory space needed to represent an arbitrary triangulation, while maintaining constant time for some basic queries. This work focuses on the connectivity information of the triangulation, rather than the geometric information (vertex coordinates), since the combinatorial data represents the main part of the storage. 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 and use stable catalogs of patches that are closed 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 that exhibits the practical gain of such methods.
Type de document :
Article dans une revue
International Journal of Computational Geometry and Applications, World Scientific Publishing, 2011, 21 (4), pp.393-402. 〈10.1142/S021819591100372X〉
Liste complète des métadonnées

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


https://hal.inria.fr/inria-00560400
Contributeur : Olivier Devillers <>
Soumis le : vendredi 28 janvier 2011 - 11:39:08
Dernière modification le : jeudi 11 janvier 2018 - 15:50:48
Document(s) archivé(s) le : mardi 6 novembre 2012 - 12:35:39

Fichiers

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

Identifiants

Collections

Citation

Luca Castelli Aleardi, Olivier Devillers, Abdelkrim Mebarki. Catalog Based Representation of 2D triangulations. International Journal of Computational Geometry and Applications, World Scientific Publishing, 2011, 21 (4), pp.393-402. 〈10.1142/S021819591100372X〉. 〈inria-00560400〉

Partager

Métriques

Consultations de la notice

412

Téléchargements de fichiers

215