Dynamically Maintaining the Persistent Homology of Time Series
Sebastiano Cultrera di Montesano, Herbert Edelsbrunner, Monika Rauch Henzinger, Lara Ost · Society for Industrial and Applied Mathematics eBooks · 2024
We present a dynamic data structure for maintaining the persistent homology of a time series of real numbers. The data structure supports local operations, including the insertion and deletion of an item and the cutting and concatenating of lists, each in time O(log n + k), in which n counts the critical items and k the changes in the augmented persistence diagram. To achieve this, we design a tailor-made tree structure with an unconventional representation, referred to as banana tree, which may be useful in its own right.