More Like this

1. Stability and Approximations for Decorated Reeb Spaces

   https://doi.org/10.4230/LIPIcs.SoCG.2024.44  

   Curry, Justin ; Mio, Washington ; Needham, Tom ; Okutan, Osman Berat ; Russold, Florian ( January 2024 , Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Mulzer, Wolfgang ; Phillips, Jeff M (Ed.)

   Given a map f:X → M from a topological space X to a metric space M, a decorated Reeb space consists of the Reeb space, together with an attribution function whose values recover geometric information lost during the construction of the Reeb space. For example, when M = ℝ is the real line, the Reeb space is the well-known Reeb graph, and the attributions may consist of persistence diagrams summarizing the level set topology of f. In this paper, we introduce decorated Reeb spaces in various flavors and prove that our constructions are Gromov-Hausdorff stable. We also provide results on approximating decorated Reeb spaces from finite samples and leverage these to develop a computational framework for applying these constructions to point cloud data. 

   more » « less
2. An Efficient Data Retrieval Parallel Reeb Graph Algorithm

   https://doi.org/10.3390/a13100258  

   Hajij, Mustafa ; Rosen, Paul ( October 2020 , Algorithms)

   null (Ed.)

   The Reeb graph of a scalar function that is defined on a domain gives a topologically meaningful summary of that domain. Reeb graphs have been shown in the past decade to be of great importance in geometric processing, image processing, computer graphics, and computational topology. The demand for analyzing large data sets has increased in the last decade. Hence, the parallelization of topological computations needs to be more fully considered. We propose a parallel augmented Reeb graph algorithm on triangulated meshes with and without a boundary. That is, in addition to our parallel algorithm for computing a Reeb graph, we describe a method for extracting the original manifold data from the Reeb graph structure. We demonstrate the running time of our algorithm on standard datasets. As an application, we show how our algorithm can be utilized in mesh segmentation algorithms. 

   more » « less
3. A Family of Metrics from the Truncated Smoothing of Reeb Graphs

   https://doi.org/10.4230/LIPIcs.SoCG.2021.22  

   Chambers, Erin Wolf ; Munch, Elizabeth ; Ophelders, Tim ( June 2021 , Forensic toxicology)

   Buchin, Kevin ; Colin de Verdi\` (Ed.)

   In this paper, we introduce an extension of smoothing on Reeb graphs, which we call truncated smoothing; this in turn allows us to define a new family of metrics which generalize the interleaving distance for Reeb graphs. Intuitively, we "chop off" parts near local minima and maxima during the course of smoothing, where the amount cut is controlled by a parameter τ. After formalizing truncation as a functor, we show that when applied after the smoothing functor, this prevents extensive expansion of the range of the function, and yields particularly nice properties (such as maintaining connectivity) when combined with smoothing for 0 ≤ τ ≤ 2ε, where ε is the smoothing parameter. Then, for the restriction of τ ∈ [0,ε], we have additional structure which we can take advantage of to construct a categorical flow for any choice of slope m ∈ [0,1]. Using the infrastructure built for a category with a flow, this then gives an interleaving distance for every m ∈ [0,1], which is a generalization of the original interleaving distance, which is the case m = 0. While the resulting metrics are not stable, we show that any pair of these for m, m' ∈ [0,1) are strongly equivalent metrics, which in turn gives stability of each metric up to a multiplicative constant. We conclude by discussing implications of this metric within the broader family of metrics for Reeb graphs. 

   more » « less
4. Metric and Path-Connectedness Properties of the Frechet Distance for Paths and Graphs

   Erin Chambers, Brittan Fasy ( August 2023 , Proceedings of the Canadian Conference on Computational Geometry)

   The Frechet distance is often used to measure distances between paths, with applications in areas ranging from map matching to GPS trajectory analysis to hand- writing recognition. More recently, the Frechet distance has been generalized to a distance between two copies of the same graph embedded or immersed in a metric space; this more general setting opens up a wide range of more complex applications in graph analysis. In this paper, we initiate a study of some of the fundamental topological properties of spaces of paths and of graphs mapped to R^n under the Frechet distance, in an effort to lay the theoretical groundwork for understanding how these distances can be used in practice. In particular, we prove whether or not these spaces, and the metric balls therein, are path-connected. 

   more » « less
5. Metric and Path-Connectedness Properties of the Fréchet Distance for Paths and Graphs

   Erin Chambers ; Fasy, Brittany Terese ; Holmgren, Benjamin ; Majhi, Sushovan ; Wenk, Carola ( July 2023 , CCCG)

   The Fréchet distance is often used to measure distances between paths, with applications in areas ranging from map matching to GPS trajectory analysis to hand- writing recognition. More recently, the Fréchet distance has been generalized to a distance between two copies of the same graph embedded or immersed in a metric space; this more general setting opens up a wide range of more complex applications in graph analysis. In this paper, we initiate a study of some of the fundamental topological properties of spaces of paths and of graphs mapped to R^n under the Fréchet distance, in an eort to lay the theoretical groundwork for understanding how these distances can be used in practice. In particular, we prove whether or not these spaces, and the metric balls therein, are path-connected. 

   more » « less