Agglomerative Clustering of Growing Squares

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

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

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(nlognloglogn)
space, supports queries in worst case O(log2n)
time, and updates in O(log5n)
amortized time. This leads to an O(nα(n)log5n)
time algorithm to solve the agglomerative clustering problem. This is a significant improvement over the current best O(n2)
time algorithms.
Original languageEnglish
Pages (from-to)216-233
Number of pages18
JournalAlgorithmica
Volume84
Issue number1
DOIs
Publication statusPublished - 2022

Keywords

  • kinetic data structures
  • Computational geometry
  • Range trees

Fingerprint

Dive into the research topics of 'Agglomerative Clustering of Growing Squares'. Together they form a unique fingerprint.

Cite this