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 :
Reports
Complete list of metadatas

Cited literature [1 references]  Display  Hide  Download

https://hal.inria.fr/inria-00070574
Contributor : Rapport de Recherche Inria <>
Submitted on : Friday, May 19, 2006 - 8:55:21 PM
Last modification on : Wednesday, March 27, 2019 - 4:41:27 PM
Long-term archiving on: Sunday, April 4, 2010 - 9:30:03 PM

Identifiers

  • HAL Id : inria-00070574, version 1

Collections

Citation

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

Share

Metrics

Record views

371

Files downloads

197