[ACM Press the 2012 symposuim - Chapel Hill, North Carolina, USA (2012.06.17-2012.06.20)] Proceedings of the 2012 symposuim on Computational Geometry - SoCG '12 - A deterministic o(m log m) time algorithm for the reeb graph

✍ Scribed by Parsa, Salman

• Book ID: 121425299
• Publisher: ACM Press
• Year: 2012
• Tongue: English
• Weight: 895 KB
• Category: Article
• ISBN: 1450312993
• DOI: 10.1145/2261250.2261289

✦ Synopsis

We present a deterministic algorithm to compute the Reeb graph of a PL real-valued function on a simplicial complex in O(m log m) time, where m is the size of the 2-skeleton. The problem reduces to dynamic graph connectivity. We obtain the running time by using offline graph connectivity which assumes that the sequence of operations is known in advance. The algorithm is implemented and experimental results are given. In addition, we reduce the offline graph connectivity problem to computing the Reeb graph.