next up previous
Next: About this document ...

Succinct representation of triangulations
with a boundary

Luca Castelli Aleardi and Olivier Devillers and Gilles Schaeffer


We consider the problem of designing succinct geometric data structures while maintaining efficient navigation operations. A data structure is said succinct if the asymptotic amount of space it uses matches the entropy of the class of structures represented.

For the case of planar triangulations with a boundary we propose a succinct representation of the combinatorial information that improves to $2.175$ bits per triangle the asymptotic amount of space required and that supports the navigation between adjacent triangles in constant time (as well as other standard operations). For triangulations with $m$ faces of a surface with genus $g$, our representation requires asymptotically an extra amount of $36(g-1)\lg m$ bits (which is negligible as long as $g\ll m/\lg

Luca Castelli Aleardi 2005-10-03