Compact representations of geometric data structures
Représentations compactes de structures de données géométriques
Résumé
We consider the problem of designing compact and succint representations for geometric data structures. As opposed to raw compression issues,the focus is here on designing data structures that preserve the possibility of answering local incidence queries in constant time, while using little as memory resources as possible. One of the main contribution of this work is to present a general algorithmic framework for designing compact representations of structures as planar graphs and 3D meshes. As application we propose some solutions for compactly representing the connectivity (combinatorial information) of some classes of local planar graphs. For planar triangulations with m faces, we propose a compact representation of the connectivity information that improves to 2:175 bits per triangle the asymptotic amount of space required and that supports navigation between adjacent triangles in constant time : this is optimal for the class of triangulations with a boundary of arbitrary sizes. For triangulations of a surface with bounded genus g, our representation is still valid and optimal, requiring O(g logm) extra bits. Such a representation can be adapted to allow local updates of the triangulation. More precisely, a triangulation with m triangles can be maintained under vertex insertions in O(1) amortized time and under vertex deletions/edge °ips in O(log2m) amortized time. We also propose the ¯rst optimal representations for 3-connected planar graphs and triangulations, which are the standard classes of graphs underlying meshes with spherical topology. Optimal means that these representations asymptotically match the respective entropy of the two classes, namely 2 bits per edge for 3-connected planar graphs, and 1:62 bits per triangle (or equivalently 3:24 bits per vertex) for triangulations. These structures allow constant time access to vertex specific data, like coordinates, but our work does not address the compression of this geometric information.
Nous considérons le problème de concevoir des représentations compactes ou succinctes de structures de données géométriques. Dans ce cadre, en plus des questions de simple compression, l'attention est portée sur l'étude de structures de données nécessitant une petite quantité de ressources mémoire et permettant de répondre à des requêtes locales en temps O(1). L'une des contributions de cette thèse consiste à proposer un cadre algorithmique général pour la conception de représentations compactes de structures telles que les graphes planaires et les maillages surfaciques. Comme application nous présentons différentes structures spécialement conçues pour représenter de manière compacte la connectivité (ou information combinatoire) de certaines classes de graphes localement planaires. Pour le cas des triangulations planaires à m faces, nous proposons une représentation compacte de l'information combinatoire nécessitant asymptotiquement 2:175 bits par triangle pour le coût en espace et qui permet la navigation entre triangles adjacents, ainsi que d'autres requêtes locales d'incidence entre sommets, en temps constant : cette structure est ainsi optimale pour la classe des triangulations ayant un bord de taille arbitraire. Une telle représentation reste valide et optimale dans le cas de triangulations d'une surface de genre g borné : O(g lgm) bits supplémentaires sont alors nécessaires. Cette représentation est bien adaptée pour faire une mise à jour locale efficace de la triangulation. Plus précisément, il est possible d'effectuer des mises à jour en temps O(1) amorti après insertion de sommets, et en temps O(log2m) amorti après suppression de sommets et flip d'arêtes. Et en ce qui concerne les triangulations et les graphes planaires 3-connexes, correspondant aux maillages triangulaires et polygonaux homéomorphes à une sphère, nous proposons les premières représentations succinctes optimales : elles atteignent l'entropie respective des deux classes, 2 bits par arête pour les graphes 3-connexes, et 1:62 bits par triangle (ou 3:24 bits par sommet) pour les triangulations. Ces structures permettent aussi l'accès en temps O(1) aux informations associées aux sommets, notamment leurs coordonnées. Cependant nous ne traitons pas ici la compression de cette information géométrique.
Loading...