Agglomerative Clustering of Growing Squares

Abstract

We study an agglomerative clustering problem motivated by interactive glyphs in geo-visualization. Consider a set of disjoint square glyphs on an interactive map. When the user zooms out, the glyphs grow in size relative to the map, possibly with different speeds. When two glyphs intersect, we wish to replace them by a new glyph that captures the information of the intersecting glyphs.

We present a fully dynamic kinetic data structure that maintains a set of \(n\) disjoint growing squares. Our data structure uses \(O(n \log n \log\log n)\) space, supports queries in worst case \(O(\log^2 n)\) time, and updates in \(O(\log^5 n)\) amortized time. This leads to an \(O(n\,\alpha(n)\log^5 n)\) time algorithm to solve the agglomerative clustering problem. This is a significant improvement over the current best \(O(n^2)\) time algorithms.

Corresponding Publications

Agglomerative Clustering of Growing Squares

Thom Castermans, Bettina Speckmann, Frank Staals, Kevin Verbeek

Proc. 2018 Latin American Theoretical Informatics Symposium, 2018

Download Local Copy View Slides Export Citation 
@incollection{zoomingsquares2018,
  author = {Castermans, Thom and Speckmann, Bettina and Staals, Frank
                 and Verbeek, Kevin},
  title = {Agglomerative Clustering of Growing Squares},
  booktitle = {Proc. 2018 Latin American Theoretical Informatics Symposium},
  editor = {Bender, Michael A. and Farach-Colton, Mart{\'i}n and Mosteiro, Miguel A.},
  series = {LNCS},
  year = {2018},
  location = {Buenos Aires, Argentina},
  numpages = {14},
  publisher = {Springer},
  category = {datastructures},
  keywords = {kinetic data structures},
  pages = {260--274},
  isbn = {978-3-319-77404-6},
  url = {https://doi.org/10.1007/978-3-319-77404-6_20},
  doi = {10.1007/978-3-319-77404-6_20},
}

Agglomerative Clustering of Growing Squares

Thom Castermans, Bettina Speckmann, Frank Staals, Kevin Verbeek

Algorithmica, 2022

Download Local Copy View Slides Export Citation 
@article{zoomingsquares2022,
  author = {Castermans, Thom and Speckmann, Bettina and Staals, Frank
                 and Verbeek, Kevin},
  title = {Agglomerative Clustering of Growing Squares},
  journal = {Algorithmica},
  volume = {84},
  number = {1},
  pages = {216--233},
  year = {2022},
  numpages = {18},
  publisher = {Springer},
  category = {datastructures},
  keywords = {kinetic data structures},
  url = {https://doi.org/10.1007/s00453-021-00873-0},
  doi = {10.1007/s00453-021-00873-0},
  project = {zoomingsquares2018},
}

Agglomerative Clustering of Growing Squares

Thom Castermans, Bettina, Speckmann, Frank Staals, Kevin Verbeek

Abstr. 34th European Workshop on Computational Geometry (EuroCG), 2017

Download Local Copy View Slides Export Citation 
@article{zoomingsquares2018_eurocg,
  author = {Castermans, Thom and Speckmann, Bettina, and Staals, Frank
                 and Verbeek, Kevin},
  title = {Agglomerative Clustering of Growing Squares},
  journal = {Abstr. 34th European Workshop on Computational Geometry (EuroCG)},
  year = {2017},
  location = {Berlin, Germany},
  numpages = {6},
  category = {datastructures},
  project = {zoomingsquares2018},
  keywords = {kinetic data structures},
  url = {https://conference.imp.fu-berlin.de/eurocg18/download/eurocg_proc.pdf},
}