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 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 faces of a surface with genus , our representation requires asymptotically an extra amount of bits (which is negligible as long as ).

Luca Castelli Aleardi 2005-10-03