Updating zigzag representatives efficiently
2026-07-17 • Computational Geometry
Computational Geometry
AI summaryⓘ
The authors address how to efficiently update zigzag persistence representatives, which are important in data analysis using topological methods. They build upon a recent method that extracts these representatives using a special decomposition called R=DV. The main challenge is handling changes in adjacency when the filtration is lengthened or shortened. Despite this, the authors show that updates can be done efficiently in quadratic time.
zigzag persistencerepresentativesfiltrationR=DV decompositionadjacencytopological data analysisquadratic timeupdate algorithms
Authors
Tamal K. Dey, Tao Hou, Dmitriy Morozov
Abstract
Computation of zigzag persistence has progressed in recent years, with results showing that complexities of many problems closely align with those in the non-zigzag setting. The major efficiency gap now lies in the updating of zigzag representatives. In this paper, we propose efficient algorithms for updating zigzag representatives based on a recent algorithm for extracting zigzag representatives from a $R=DV$ decomposition of a constructed non-zigzag. The main difficulty for designing our update algorithms lies in the adjacency change occurring in two operations that elongate or shorten a filtration. Despite the adjacency change, we find that the update can still be done efficiently in quadratic time.