Measuring distance between Reeb graphs

U. Bauer, X. Ge, Y. Wang, in:, Proceedings of the Annual Symposium on Computational Geometry, ACM, 2014, pp. 464–473.


Conference Paper | Published | English
Author
; ;
Department
Abstract
We propose a metric for Reeb graphs, called the functional distortion distance. Under this distance, the Reeb graph is stable against small changes of input functions. At the same time, it remains discriminative at differentiating input functions. In particular, the main result is that the functional distortion distance between two Reeb graphs is bounded from below by the bottleneck distance between both the ordinary and extended persistence diagrams for appropriate dimensions. As an application of our results, we analyze a natural simplification scheme for Reeb graphs, and show that persistent features in Reeb graph remains persistent under simplification. Understanding the stability of important features of the Reeb graph under simplification is an interesting problem on its own right, and critical to the practical usage of Reeb graphs. Copyright is held by the owner/author(s).
Publishing Year
Date Published
2014-06-01
Proceedings Title
Proceedings of the Annual Symposium on Computational Geometry
Acknowledgement
National Science Foundation under grants CCF-1319406, CCF-1116258.
Page
464 - 473
Conference
SoCG: Symposium on Computational Geometry
Conference Location
Kyoto, Japan
Conference Date
2014-06-08 – 2014-06-11
IST-REx-ID

Cite this

Bauer U, Ge X, Wang Y. Measuring distance between Reeb graphs. In: Proceedings of the Annual Symposium on Computational Geometry. ACM; 2014:464-473. doi:10.1145/2582112.2582169
Bauer, U., Ge, X., & Wang, Y. (2014). Measuring distance between Reeb graphs. In Proceedings of the Annual Symposium on Computational Geometry (pp. 464–473). Kyoto, Japan: ACM. https://doi.org/10.1145/2582112.2582169
Bauer, Ulrich, Xiaoyin Ge, and Yusu Wang. “Measuring Distance between Reeb Graphs.” In Proceedings of the Annual Symposium on Computational Geometry, 464–73. ACM, 2014. https://doi.org/10.1145/2582112.2582169.
U. Bauer, X. Ge, and Y. Wang, “Measuring distance between Reeb graphs,” in Proceedings of the Annual Symposium on Computational Geometry, Kyoto, Japan, 2014, pp. 464–473.
Bauer U, Ge X, Wang Y. 2014. Measuring distance between Reeb graphs. Proceedings of the Annual Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry 464–473.
Bauer, Ulrich, et al. “Measuring Distance between Reeb Graphs.” Proceedings of the Annual Symposium on Computational Geometry, ACM, 2014, pp. 464–73, doi:10.1145/2582112.2582169.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar