Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

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

Buchin, Kevin and (Ed.)We show how a filtration of Delaunay complexes can be used to approximate the persistence diagram of the distance to a point set in ℝ^d. Whereas the full Delaunay complex can be used to compute this persistence diagram exactly, it may have size O(n^⌈d/2⌉). In contrast, our construction uses only O(n) simplices. The central idea is to connect Delaunay complexes on progressively denser subsamples by considering the flips in an incremental construction as simplices in d+1 dimensions. This approach leads to a very simple and straightforward proof of correctness in geometric terms, because the final filtration is dual to a (d+1)dimensional Voronoi construction similar to the standard Delaunay filtration. We also, show how this complex can be efficiently constructed.more » « less

Buchin, Kevin and (Ed.)Given a family F of kelement sets, S₁,…,S_r ∈ F form an rsunflower if S_i ∩ S_j = S_{i'} ∩ S_{j'} for all i ≠ j and i' ≠ j'. According to a famous conjecture of Erdős and Rado (1960), there is a constant c = c(r) such that if F ≥ c^k, then F contains an rsunflower. We come close to proving this conjecture for families of bounded VapnikChervonenkis dimension, VCdim(F) ≤ d. In this case, we show that rsunflowers exist under the slightly stronger assumption F ≥ 2^{10k(dr)^{2log^{*} k}}. Here, log^* denotes the iterated logarithm function. We also verify the ErdősRado conjecture for families F of bounded Littlestone dimension and for some geometrically defined set systems.more » « less