Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke





.......................

.......................


Publications [#353264] of Woojin Kim

Papers Published

  1. Kim, W; Mémoli, F, Formigrams: Clustering summaries of dynamic data, Proceedings of the 30th Canadian Conference on Computational Geometry, Cccg 2018 (January, 2018), pp. 180-188
    (last updated on 2023/07/05)

    Abstract:
    When studying flocking/swarming behaviors in animals one is interested in quantifying and comparing the dynamics of the clustering induced by the coalescence and disbanding of animals in different groups. Motivated by this, we propose a summarization of time-dependent metric data which captures their time-dependent clustering features which we call formigrams. These set-valued functions generalize the notion of dendrogram, a prevalent object in the context of hierarchical clustering. Also, we define a metric on formigrams for quantifying the degree of structural difference between any two given formigrams. In particular, the restriction of this metric to the collection of dendrograms recovers twice the Gromov-Hausdorff distance between the ultrametric spaces associated to the dendrograms. This fact enables us to show that constant factor approximations to the metric on formigrams cannot be obtained in polynomial time. Finally, we investigate a sufficient condition for time-dependent metric spaces to be summarized into formigrams. In addition, we prove that this summarization process is stable under perturbations in the input time-dependent metric data.

 

dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320