Luca Castelli Aleardi and Olivier Devillers and Gilles Schaeffer
Precisely, we show how a succinct representation of a triangulation with triangles can be maintained under vertex insertions in amortized time and under vertex deletions/edge flips in amortized time.
Our structure achieves the information theory bound for the storage for the class of triangulations with a boundary, requiring asymptotically bits, and supports adjacency queries between triangles in time (an extra amount of bits are needed for representing triangulations of genus surfaces).