Agglomerative clustering of growing squares

Thom Castermans; Bettina Speckmann; Frank Staals; Kevin Verbeek

doi:10.1007/978-3-319-77404-6_20

Agglomerative clustering of growing squares

Thom Castermans, Bettina Speckmann, Frank Staals, Kevin Verbeek

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

3 Citations (Scopus)

68 Downloads (Pure)

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³ n) time, and updates in O(log⁷n) amortized time. This leads to an O(n α(n) log⁷n) time algorithm (where α is the inverse Ackermann function) to solve the agglomerative clustering problem, which is a significant improvement over the straightforward O(n² 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	https://doi.org/10.1007/978-3-319-77404-6_20
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	http://latin2018.dc.uba.ar/

Access to Document

10.1007/978-3-319-77404-6_20

agglomerative-clustering-growingFinal author version , 668 KBLicence: Unspecified

Link to publication in Scopus

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

Cite this

Castermans, T., Speckmann, B., Staals, F., & Verbeek, K. (2018). Agglomerative clustering of growing squares. In M. A. Bender, M. Farach-Colton, & M. A. Mosteiro (Eds.), 13th Latin American Theoretical INformatics Symposium (LATIN) (pp. 260-274). (Lecture Notes in Computer Science; Vol. 10807), (Theoretical Computer Science and General Issues; Vol. 10807). Springer. https://doi.org/10.1007/978-3-319-77404-6_20

@inproceedings{f3f584d4561140088efedb20cc777878,

title = "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)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.",

author = "Thom Castermans and Bettina Speckmann and Frank Staals and Kevin Verbeek",

year = "2018",

month = jan,

day = "1",

doi = "10.1007/978-3-319-77404-6_20",

language = "English",

isbn = "9783319774039",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "260--274",

editor = "M.A. Bender and M. Farach-Colton and M.A. Mosteiro",

booktitle = "13th Latin American Theoretical INformatics Symposium (LATIN)",

address = "Germany",

note = "13th Latin American Theoretical INformatics Symposium (LATIN 2018), LATIN 2018 ; Conference date: 16-04-2018 Through 19-04-2018",

url = "http://latin2018.dc.uba.ar/",

}

Castermans, T , Speckmann, B, Staals, F & Verbeek, K 2018, Agglomerative clustering of growing squares. in MA Bender, M Farach-Colton & MA Mosteiro (eds), 13th Latin American Theoretical INformatics Symposium (LATIN). Lecture Notes in Computer Science, vol. 10807, Theoretical Computer Science and General Issues, vol. 10807, Springer, Berlin, pp. 260-274, 13th Latin American Theoretical INformatics Symposium (LATIN 2018), Buenos Aires, Argentina, 16/04/18. https://doi.org/10.1007/978-3-319-77404-6_20

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

N1 - Conference code: 13

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

T2 - 13th Latin American Theoretical INformatics Symposium (LATIN 2018)

Y2 - 16 April 2018 through 19 April 2018

ER -

Castermans T , Speckmann B, Staals F, Verbeek K. Agglomerative clustering of growing squares. In Bender MA, Farach-Colton M, Mosteiro MA, editors, 13th Latin American Theoretical INformatics Symposium (LATIN). Berlin: Springer. 2018. p. 260-274. (Lecture Notes in Computer Science). (Theoretical Computer Science and General Issues). https://doi.org/10.1007/978-3-319-77404-6_20