# Compact representation of triangulations

1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : We consider the problem of representing compact geometric data structures maintaining an efficient implementation of navigation operations. For the case of 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. For triangulations with $m$ faces of a surface with genus $g$, our representation requires asymptotically an extra amount of $36(g-1)\lgm$ bits. The structure also allows constant time access to vertex specific data, like coordinates, but the paper does not address the compression of this geometric information.
Keywords :
Document type :
Reports
Domain :

Cited literature [1 references]

https://hal.inria.fr/inria-00070574
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Friday, May 19, 2006 - 8:55:21 PM
Last modification on : Friday, February 4, 2022 - 3:17:02 AM
Long-term archiving on: : Sunday, April 4, 2010 - 9:30:03 PM

### Identifiers

• HAL Id : inria-00070574, version 1

### Citation

Luca Castelli Aleardi, Olivier Devillers, Gilles Schaeffer. Compact representation of triangulations. [Research Report] RR-5433, INRIA. 2006, pp.20. ⟨inria-00070574⟩

Record views