The Offset Filtration of Convex Objects

We consider offsets of a union of convex objects. We aim for a filtration, a sequence of nested cell complexes, that captures the topological evolution of the offsets for increasing radii. We describe methods to compute a filtration based on the Voronoi diagram of the given convex objects. We prove that, in two and three dimensions, the size of the filtration is proportional to the size of the Voronoi diagram. Our algorithm runs in Θ(n logn) in the 2-dimensional case and in expected time O(n3 + e), for any e > 0, in the 3-dimensional case. Our approach is inspired by alpha-complexes for point sets, but requires more involved machinery and analysis primarily since Voronoi regions of general convex objects do not form a good cover. We show by experiments that our approach results in a similarly fast and topologically more stable method compared to approximating the input by point samples.

• Publication year

  2014

• Venue

  Embedded Systems and Applications

• Publication date

  2014-07-23

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/978-3-662-48350-3_59arXiv 1407.6132
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Phat - Persistent Homology Algorithms Toolbox

  2014cited by this paper
• Approximating persistent homology in Euclidean space through collapses

  2014cited by this paper
• Topology of viral evolution

  2013cited by this paper
• Graph induced complex on point data

  2013cited by this paper
• Persistent Homology: Theory and Practice

  2013cited by this paper
• Alpha, Betti and the Megaparsec Universe: On the Topology of the Cosmic Web

  2013cited by this paper
• Clear and Compress: Computing Persistent Homology in Chunks

  2013cited by this paper
• The Compressed Annotation Matrix: An Efficient Data Structure for Computing Persistent Cohomology

  2013cited by this paper
• Approximate Čech Complex in Low and High Dimensions

  2013cited by this paper
• Towards exact numerical Voronoi diagrams

  2012cited by this paper
• Linear-Size Approximations to the Vietoris–Rips Filtration

  2012cited by this paper
• The Structure and Stability of Persistence Modules

  2012cited by this paper
• Persistent homology and partial similarity of shapes

  2012cited by this paper
• Multinerves and helly numbers of acyclic families

  2012cited by this paper
• An output-sensitive algorithm for persistent homology

  2011cited by this paper
• Vroni and ArcVroni: Software for and Applications of Voronoi Diagrams in Science and Engineering

  2011cited by this paper
• Zigzag persistent homology in matrix multiplication time

  2011cited by this paper
• Persistence-based segmentation of deformable shapes

  2010cited by this paper
• Constructing the Exact Voronoi Diagram of Arbitrary Lines in Space

  2010cited by this paper
• Proximity of persistence modules and their diagrams

  2009cited by this paper
• Persistence Diagrams of Cortical Surface Data

  2009cited by this paper
• Topology and data

  2009cited by this paper
• Extending Persistence Using Poincaré and Lefschetz Duality

  2009cited by this paper
• An efficient implementation of Delaunay triangulations in medium dimensions

  2008cited by this paper
• Reeb graphs for shape analysis and applications

  2008cited by this paper
• Towards persistence-based reconstruction in euclidean spaces

  2007cited by this paper
• Effective Computational Geometry for Curves and Surfaces Chapter 7 Computational Topology : An Introduction

  2007cited by this paper
• Stability of Persistence Diagrams

  2005cited by this paper
• Computing Persistent Homology

  2004cited by this paper
• Voronoi Diagrams and Delaunay Triangulations

  2004cited by this paper
• Persistence barcodes for shapes

  2004cited by this paper
• The Voronoi Diagram of Planar Convex Objects

  2003cited by this paper
• Delaunay refinement algorithms for triangular mesh generation

  2002cited by this paper
• Almost tight upper bounds for vertical decompositions in four dimensions

  2001cited by this paper
• Topological Persistence and Simplification

  2000cited by this paper
• Pipes, Cigars, and Kreplach: the Union of Minkowski Sums in Three Dimensions

  1999cited by this paper
• Computational geometry: algorithms and applications

  1997cited by this paper
• A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation

  1995cited by this paper
• Computing envelopes in four dimensions with applications

  1994cited by this paper
• Robust Construction of the Voronoi Diagram of a Polyhedron

  1993cited by this paper
• An incremental algorithm for Betti numbers of simplicial complexes

  1993cited by this paper
• A subexponential bound for linear programming

  1992cited by this paper
• AnO(n logn) algorithm for the voronoi diagram of a set of simple curve segments

  1987cited by this paper
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles

  1986cited by this paper
• ELEMENTS OF ALGEBRAIC TOPOLOGY

  1972cited by this paper
• private communication

  1969cited by this paper

• On metrics for analysis of functional data on geometric domains

  2023cites this paper
• Persistent homology in ℓ∞ metric

  2022cites this paper
• Persistent Homology in $\ell_{\infty}$ Metric

  2020influential citation
• The Topology of Skeletons and Offsets

  2018cites this paper
• Offset hypersurfaces and persistent homology of algebraic varieties

  2018cites this paper
• Persistent Homology – State of the art and challenges

  2016cites this paper
• Young Reseachers Forum: Book of Abstracts

  2015cites this paper