 Award ID(s):
 2017980
 NSFPAR ID:
 10422656
 Editor(s):
 Goaoc, Xavier and
 Date Published:
 Journal Name:
 38th International Symposium on Computational Geometry (SoCG 2022)
 Page Range / eLocation ID:
 60:160:15
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

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 wellknown 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 GromovHausdorff 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

Abstract We study a family of invariants of compact metric spaces that combines the Curvature Sets defined by Gromov in the 1980 s with Vietoris–Rips Persistent Homology. For given integers
and$$k\ge 0$$ $k\ge 0$ we consider the dimension$$n\ge 1$$ $n\ge 1$k Vietoris–Rips persistence diagrams ofall subsets of a given metric space with cardinality at mostn . We call these invariantspersistence sets and denote them as . We first point out that this family encompasses the usual Vietoris–Rips diagrams. We then establish that (1) for certain range of values of the parameters$${\textbf{D}}_{n,k}^{\textrm{VR}}$$ ${D}_{n,k}^{\text{VR}}$n andk , computing these invariants is significantly more efficient than computing the usual Vietoris–Rips persistence diagrams, (2) these invariants have very good discriminating power and, in many cases, capture information that is imperceptible through standard Vietoris–Rips persistence diagrams, and (3) they enjoy stability properties analogous to those of the usual Vietoris–Rips persistence diagrams. We precisely characterize some of them in the case of spheres and surfaces with constant curvature using a generalization of Ptolemy’s inequality. We also identify a rich family of metric graphs for which fully recovers their homotopy type by studying splitmetric decompositions. Along the way we prove some useful properties of Vietoris–Rips persistence diagrams using Mayer–Vietoris sequences. These yield a geometric algorithm for computing the Vietoris–Rips persistence diagram of a space$${\textbf{D}}_{4,1}^{\textrm{VR}}$$ ${D}_{4,1}^{\text{VR}}$X with cardinality with quadratic time complexity as opposed to the much higher cost incurred by the usual algebraic algorithms relying on matrix reduction.$$2k+2$$ $2k+2$ 
Buchin, Kevin and (Ed.)Given a persistence diagram with n points, we give an algorithm that produces a sequence of n persistence diagrams converging in bottleneck distance to the input diagram, the ith of which has i distinct (weighted) points and is a 2approximation to the closest persistence diagram with that many distinct points. For each approximation, we precompute the optimal matching between the ith and the (i+1)st. Perhaps surprisingly, the entire sequence of diagrams as well as the sequence of matchings can be represented in O(n) space. The main approach is to use a variation of the greedy permutation of the persistence diagram to give good Hausdorff approximations and assign weights to these subsets. We give a new algorithm to efficiently compute this permutation, despite the high implicit dimension of points in a persistence diagram due to the effect of the diagonal. The sketches are also structured to permit fast (linear time) approximations to the Hausdorff distance between diagrams  a lower bound on the bottleneck distance. For approximating the bottleneck distance, sketches can also be used to compute a linearsize neighborhood graph directly, obviating the need for geometric data structures used in stateoftheart methods for bottleneck computation.more » « less

null (Ed.)Abstract The uniformization and hyperbolization transformations formulated by Bonk et al. in “Uniformizing Gromov Hyperbolic Spaces” , Astérisque, vol 270 (2001), dealt with geometric properties of metric spaces. In this paper we consider metric measure spaces and construct a parallel transformation of measures under the uniformization and hyperbolization procedures. We show that if a locally compact roughly starlike Gromov hyperbolic space is equipped with a measure that is uniformly locally doubling and supports a uniformly local p Poincaré inequality, then the transformed measure is globally doubling and supports a global p Poincaré inequality on the corresponding uniformized space. In the opposite direction, we show that such global properties on bounded locally compact uniform spaces yield similar uniformly local properties for the transformed measures on the corresponding hyperbolized spaces. We use the above results on uniformization of measures to characterize when a Gromov hyperbolic space, equipped with a uniformly locally doubling measure supporting a uniformly local p Poincaré inequality, carries nonconstant globally defined p harmonic functions with finite p energy. We also study some geometric properties of Gromov hyperbolic and uniform spaces. While the Cartesian product of two Gromov hyperbolic spaces need not be Gromov hyperbolic, we construct an indirect product of such spaces that does result in a Gromov hyperbolic space. This is done by first showing that the Cartesian product of two bounded uniform domains is a uniform domain.more » « less

null (Ed.)In this paper, we study the asymptotic behavior of BV functions in complete metric measure spaces equipped with a doubling measure supporting a 1Poincare inequality. We show that at almost every point x outside the Cantor and jump parts of a BV function, the asymptotic limit of the function is a Lipschitz continuous function of least gradient on a tangent space to the metric space based at x. We also show that, at codimension 1 Hausdorff measure almost every measuretheoretic boundary point of a set E of finite perimeter, there is an asymptotic limit set (E)∞ corresponding to the asymptotic expansion of E and that every such asymptotic limit (E)∞ is a quasiminimal set of finite perimeter. We also show that the perimeter measure of (E)∞ is Ahlfors codimension 1 regular.more » « less