Maintaining reeb graphs of triangulated 2-manifolds
Let M be a triangulated, orientable 2-manifold of genus g without boundary, and let h be a height function over M that is linear within each triangle. We present a kinetic data structure (KDS) for maintaining the Reeb graph R of h as the heights of M’s vertices vary continuously with time. Assuming the heights of two vertices of M become equal only O(1) times, the KDS processes O((? + g)n polylog n) events; n is the number of vertices in M, and ? is the number of external events which change the combinatorial structure of R. Each event is processed in O(log2 n) time, and the total size of our KDS is O(gn). The KDS can be extended to maintain an augmented Reeb graph as well.
Agarwal, PK; Fox, K; Nath, A
Volume / Issue
International Standard Serial Number (ISSN)
International Standard Book Number 13 (ISBN-13)
Digital Object Identifier (DOI)