Skip to Main content Skip to Navigation

Compact representation of triangulations

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.
Document type :
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download
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


  • HAL Id : inria-00070574, version 1



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



Record views


Files downloads