Agglomerative clustering of growing squares

Thom Castermans, Bettina Speckmann, Frank Staals, Kevin Verbeek

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)
117 Downloads (Pure)


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)2) space, supports queries in worst case O(log3 n) time, and updates in O(log7 n) amortized time. This leads to an O(n α(n) log7 n) time algorithm (where α is the inverse Ackermann function) to solve the agglomerative clustering problem, which is a significant improvement over the straightforward O(n2 log n) time algorithm.

Original languageEnglish
Title of host publication13th Latin American Theoretical INformatics Symposium (LATIN)
EditorsM.A. Bender, M. Farach-Colton, M.A. Mosteiro
Place of PublicationBerlin
Number of pages15
ISBN (Print)9783319774039
Publication statusPublished - 1 Jan 2018
Event13th Latin American Theoretical INformatics Symposium (LATIN 2018) - Buenos Aires, Argentina
Duration: 16 Apr 201819 Apr 2018
Conference number: 13

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349
NameTheoretical Computer Science and General Issues


Conference13th Latin American Theoretical INformatics Symposium (LATIN 2018)
Abbreviated titleLATIN 2018
CityBuenos Aires
Internet address


Dive into the research topics of 'Agglomerative clustering of growing squares'. Together they form a unique fingerprint.

Cite this