Dynamic updates of succinct triangulations
Luca Castelli Aleardi, Olivier Devillers, Gilles Schaeffer · 2005
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).