Maintaining reeb graphs of triangulated 2-manifolds

Conference Paper

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.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Fox, K; Nath, A

Published Date

  • January 1, 2018

Published In

Volume / Issue

  • 93 /

International Standard Serial Number (ISSN)

  • 1868-8969

International Standard Book Number 13 (ISBN-13)

  • 9783959770552

Digital Object Identifier (DOI)

  • 10.4230/LIPIcs.FSTTCS.2017.8

Citation Source

  • Scopus