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)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 language | English |
|---|---|
| Title of host publication | 13th Latin American Theoretical INformatics Symposium (LATIN) |
| Editors | M.A. Bender, M. Farach-Colton, M.A. Mosteiro |
| Place of Publication | Berlin |
| Publisher | Springer |
| Pages | 260-274 |
| Number of pages | 15 |
| ISBN (Print) | 9783319774039 |
| DOIs | |
| Publication status | Published - 1 Jan 2018 |
| Event | 13th Latin American Theoretical INformatics Symposium (LATIN 2018) - Buenos Aires, Argentina Duration: 16 Apr 2018 → 19 Apr 2018 Conference number: 13 http://latin2018.dc.uba.ar/ |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Volume | 10807 |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
| Name | Theoretical Computer Science and General Issues |
|---|---|
| Volume | 10807 |
Conference
| Conference | 13th Latin American Theoretical INformatics Symposium (LATIN 2018) |
|---|---|
| Abbreviated title | LATIN 2018 |
| Country | Argentina |
| City | Buenos Aires |
| Period | 16/04/18 → 19/04/18 |
| Internet address |
Fingerprint
Cite this
}
Agglomerative clustering of growing squares. / Castermans, Thom; Speckmann, Bettina; Staals, Frank; Verbeek, Kevin.
13th Latin American Theoretical INformatics Symposium (LATIN). ed. / M.A. Bender; M. Farach-Colton; M.A. Mosteiro. Berlin : Springer, 2018. p. 260-274 (Lecture Notes in Computer Science; Vol. 10807), (Theoretical Computer Science and General Issues; Vol. 10807).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review
TY - GEN
T1 - Agglomerative clustering of growing squares
AU - Castermans, Thom
AU - Speckmann, Bettina
AU - Staals, Frank
AU - Verbeek, Kevin
PY - 2018/1/1
Y1 - 2018/1/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85045383916&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-77404-6_20
DO - 10.1007/978-3-319-77404-6_20
M3 - Conference contribution
AN - SCOPUS:85045383916
SN - 9783319774039
T3 - Lecture Notes in Computer Science
SP - 260
EP - 274
BT - 13th Latin American Theoretical INformatics Symposium (LATIN)
A2 - Bender, M.A.
A2 - Farach-Colton, M.
A2 - Mosteiro, M.A.
PB - Springer
CY - Berlin
ER -