Skip to Main content Skip to Navigation

Implantation de structures de données compactes pour les triangulations

Abdelkrim Mebarki 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : Modeling geometric ob jects is inescapable in various domains and applications. The development of acquisition and storage tools has produced a huge increase of the volumes used to store these ob jects. Many disciplines aim to reduce the size of these volumes ; such as compression, which tries to compress the volume, and the elaboration of theoretical compact data structures that minimize the space required for the representation. The goal of this thesis is to design, and evaluate practical and workable solutions for compact representations of triangulations. To do this, two issues has to be explored : modify the internal memory representation of the geometric ob jects, and redefine the abstract types associated to the geometric ob jects. The first solution proposed uses indices of an arbitrary length, instead of absolute references. The gain depends on the size of the triangulation, and the length of the memory word too. The main disadvantage of this solution is the high cost in terms of running time. The second solution uses stable catalogs. The structure gathers triangles into packages, and represents the triangulation as a decomposition of such packages. The number of multiple references to the vertices, and the number of reciprocal references between neighbors are clearly reduced. The results are interesting, and the running time is not dramatically affected by the added indirection levels. The third solution decomposes the triangulation into many sub-triangulations. The references in a sub-triangulation are coded using a reduced number of bits in comparison with the absolute references. The results of this technique are promising, and could be improved using other methods such as the relative coding of references, and sharing common vertex data between different sub-triangulations. The elaboration of compact data structures needs more attention, and several issues have to be explored in order to improve the solutions proposed.
Document type :
Complete list of metadata

Cited literature [108 references]  Display  Hide  Download
Contributor : Olivier Devillers <>
Submitted on : Monday, November 3, 2008 - 10:18:57 AM
Last modification on : Wednesday, July 25, 2018 - 1:22:52 AM
Long-term archiving on: : Monday, June 7, 2010 - 10:38:31 PM


  • HAL Id : tel-00336178, version 1



Abdelkrim Mebarki. Implantation de structures de données compactes pour les triangulations. Informatique [cs]. Université Nice Sophia Antipolis, 2008. Français. ⟨tel-00336178⟩



Record views


Files downloads