The Kinetic Hourglass Data Structure for Computing the Bottleneck Distance of Dynamic Data

Abstract

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$.