2017/07/31 by Tamal K. Dey, Dey, Tamal K., Alfred Rossi +3 · 1 citation
Computer Science · Engineering · #Advanced Numerical Analysis Techniques #Computational Geometry (cs.CG) #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #I.5.3 #Topological and Geometric Data Analysis #cs.CG #cs.DS
paper · pdf · doi:10.48550/arxiv.1707.09904
14 pages, 4 figures
openalex publication_date 2017/07/31 · arxiv created 2017/10/19 · arxiv updated 2017/10/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study hierarchical clusterings of metric spaces that change over time. This is a natural geometric primitive for the analysis of dynamic data sets. Specifically, we introduce and study the problem of finding a temporally coherent sequence of hierarchical clusterings from a sequence of unlabeled point sets. We encode the clustering objective by embedding each point set into an ultrametric space, which naturally induces a hierarchical clustering of the set of points. We enforce temporal coherence among the embeddings by finding correspondences between successive pairs of ultrametric spaces which exhibit small distortion in the Gromov-Hausdorff sense. We present both upper and lower bounds on the approximability of the resulting optimization problems.