The Kinetic Hourglass Data Structure for Computing the Bottleneck Distance of Dynamic Data
This work addresses the computational challenge of maintaining bottleneck distances for continuously moving geometric objects, which is relevant to computational geometry and topological data analysis, but the contribution appears incremental.
The authors introduce the kinetic hourglass, a novel kinetic data structure for computing the bottleneck distance of dynamic data, and apply it to compute the bottleneck distance between persistent homology transforms of shapes in ℝ². No concrete performance numbers are provided.
The kinetic data structure (KDS) framework is a powerful tool for maintaining various geometric configurations of continuously moving objects. In this work, we introduce the kinetic hourglass, a novel KDS implementation designed to compute the bottleneck distance for geometric matching problems. We detail the events and updates required for handling general graphs, accompanied by a complexity analysis. Furthermore, we demonstrate the utility of the kinetic hourglass by applying it to compute the bottleneck distance between two persistent homology transforms (PHTs) derived from shapes in $\mathbb{R}^2$, which are topological summaries obtained by computing persistent homology from every direction in $\mathbb{S}^1$.