HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Dynamic updates of succinct triangulations

Abstract : In a recent article, we presented a succinct representation of triangulations that supports efficient navigation operations. Here this representation is improved to allow for efficient local updates of the triangulations. Precisely, we show how a succinct representation of a triangulation with $m$ triangles can be maintained under vertex insertions in $O(1)$ amortized time and under vertex deletions/edge flips in $O(\lg^{2} m)$ amortized time. Our structure achieves the information theory bound for the storage for the class of triangulations with a boundary, requiring asymptotically $2.17m+o(m)$ bits, and supports adjacency queries between triangles in $O(1)$ time (an extra amount of $O(g\lg m)$ bits are needed for representing triangulations of genus $g$ surfaces).
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download

https://hal.inria.fr/inria-00001187
Contributor : Olivier Devillers Connect in order to contact the contributor
Submitted on : Wednesday, April 12, 2006 - 2:55:22 PM
Last modification on : Friday, February 4, 2022 - 3:15:46 AM
Long-term archiving on: : Saturday, April 3, 2010 - 10:10:15 PM

Files

Identifiers

  • HAL Id : inria-00001187, version 1

Collections

Citation

Luca Castelli Aleardi, Olivier Devillers, Gilles Schaeffer. Dynamic updates of succinct triangulations. 18th Canadian Conference on Computational Geometry, 2005, Windsor, Canada, France. ⟨inria-00001187⟩

Share

Metrics

Record views

104

Files downloads

105