The Offset Filtration of Convex Objects

DOI10.1007/978-3-662-48350-3_59MaRDI QIDQ3452834zbMATH OpenOpenAlexFDO

Authors Michael Kerber, Doron Shaharabani, Dan Halperin

Publication date 19 November 2015

Published in Algorithms - ESA 2015 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1407.6132

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational aspects related to convexity (52B55) Relations of manifolds and cell complexes with computer and data science (57Z25)

Abstract: 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 partition with respect to 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 $Theta(nlogn)$ in the $2$-dimensional case and in expected time $O(n^{3+epsilon})$, for any $epsilon>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 for computing a filtration compared to approximating the input by point samples.

Recommendations

• scientific article; zbMATH DE number 89761
• The Geometry of Filtering
• scientific article; zbMATH DE number 1947448
• scientific article; zbMATH DE number 4165895
• Convolution filters for polygons and the Petr-Douglas-Neumann theorem
• The structure of convexors
• Surface reconstruction by offset surface filtering
• Filters in topology optimization

Cites work

• scientific article; zbMATH DE number 2103273 (Why is no real title available?)
• scientific article; zbMATH DE number 1424293 (Why is no real title available?)
• scientific article; zbMATH DE number 1433426 (Why is no real title available?)
• Almost tight upper bounds for lower envelopes in higher dimensions
• An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments
• Approximate Čech Complex in Low and High Dimensions
• Approximating persistent homology in Euclidean space through collapses
• Clear and compress: computing persistent homology in chunks
• Computational topology. An introduction
• Computing Envelopes in Four Dimensions with Applications
• Computing persistent homology
• Constructing the exact Voronoi diagram of arbitrary lines in three-dimensional space. With fast point-location
• Multinerves and Helly numbers of acyclic families
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• PHAT -- persistent homology algorithms toolbox
• Persistent homology: theory and practice
• Reeb graphs for shape analysis and applications
• The Offset Filtration of Convex Objects
• Topological persistence and simplification
• Topology and data
• Towards persistence-based reconstruction in euclidean spaces

Cited in

(6)

• New filtering for the cumulative constraint in the context of non-overlapping rectangles
• On metrics for analysis of functional data on geometric domains
• Offset hypersurfaces and persistent homology of algebraic varieties
• scientific article; zbMATH DE number 89761 (Why is no real title available?)
• Persistent homology in \(\ell_\infty\) metric
• The Offset Filtration of Convex Objects

Describes a project that uses

Uses Software

• PHAT
• CGAL

This page was built for publication: The Offset Filtration of Convex Objects

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3452834)