Videos

Measuring Distance Between Reeb Graphs

Presenter
October 28, 2013
Keywords:
  • Geometric and topological
  • Graph
MSC:
  • 05C10
Abstract
One of the prevailing ideas in geometric and topological data analysis is to provide descriptors that encode useful information about hidden objects from observed data. The Reeb graph is one such descriptor for a given scalar function. The Reeb graph provides a simple yet meaningful abstraction of the input domain, and can also be computed efficiently. Given the popularity of the Reeb graph in applications, it is important to understand its stability and robustness with respect to changes in the input function, as well as to be able to compare the Reeb graphs resulting from different functions. In this paper, we propose a metric for Reeb graphs, called the functional distortion distance. Under this distance measure, 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 (and thus more discriminative than) the bottleneck distance between both the ordinary and extended persistence diagrams for appropriate dimensions. In this talk, I will describe the functional distortion distance for Reeb graph, its properties, and an application based on these properties. This is joint work with Ulrich Bauer and Xiaoyin Ge.