{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:50Z","timestamp":1740109310490,"version":"3.37.3"},"reference-count":10,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,11,20]],"date-time":"2021-11-20T00:00:00Z","timestamp":1637366400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,11,20]],"date-time":"2021-11-20T00:00:00Z","timestamp":1637366400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Netherlands Organisation for Scientific Research","doi-asserted-by":"crossref","award":["314.99.117","639.023.208"],"award-info":[{"award-number":["314.99.117","639.023.208"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003246","name":"Netherlands Organisation for Scientific Research","doi-asserted-by":"crossref","award":["639.021.541","612.001.651"],"award-info":[{"award-number":["639.021.541","612.001.651"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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 <jats:italic>n<\/jats:italic> disjoint growing squares. Our data structure uses <jats:inline-formula><jats:alternatives><jats:tex-math>$$O\\bigl (n \\log n \\log \\log n\\bigr )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> space, supports queries in worst case <jats:inline-formula><jats:alternatives><jats:tex-math>$$O\\bigl (\\log ^2 n\\bigr )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:msup>\n                      <mml:mo>log<\/mml:mo>\n                      <mml:mn>2<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time, and updates in <jats:inline-formula><jats:alternatives><jats:tex-math>$$O\\bigl (\\log ^5 n\\bigr )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:msup>\n                      <mml:mo>log<\/mml:mo>\n                      <mml:mn>5<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> amortized time. This leads to an <jats:inline-formula><jats:alternatives><jats:tex-math>$$O\\bigl (n\\,\\alpha (n)\\log ^5 n\\bigr )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mspace\/>\n                    <mml:mi>\u03b1<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:msup>\n                      <mml:mo>log<\/mml:mo>\n                      <mml:mn>5<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time algorithm to solve the agglomerative clustering problem. This is a significant improvement over the current best <jats:inline-formula><jats:alternatives><jats:tex-math>$$O\\bigl (n^2\\bigr )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mn>2<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mrow>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time algorithms.<\/jats:p>","DOI":"10.1007\/s00453-021-00873-0","type":"journal-article","created":{"date-parts":[[2021,11,20]],"date-time":"2021-11-20T05:02:30Z","timestamp":1637384550000},"page":"216-233","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Agglomerative Clustering of Growing Squares"],"prefix":"10.1007","volume":"84","author":[{"given":"Thom","family":"Castermans","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8514-7858","authenticated-orcid":false,"given":"Bettina","family":"Speckmann","sequence":"additional","affiliation":[]},{"given":"Frank","family":"Staals","sequence":"additional","affiliation":[]},{"given":"Kevin","family":"Verbeek","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,11,20]]},"reference":[{"key":"873_CR1","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Kaplan, H., Sharir, M.: Kinetic and dynamic data structures for closest pair and all nearest neighbors. ACM Trans. Algorith 5(1), 4:1\u20134:37 (2008)","DOI":"10.1145\/1435375.1435379"},{"key":"873_CR2","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/j.comgeo.2019.02.001","volume":"80","author":"HK Ahn","year":"2019","unstructured":"Ahn, H.K., Bae, S.W., Choi, J., Korman, M., Mulzer, W., Oh, E., Park, J.W., van Renssen, A., Vigneron, A.: Faster algorithms for growing prioritized disks and rectangles. Comput. Geom. 80, 23\u201339 (2019)","journal-title":"Comput. Geom."},{"issue":"2","key":"873_CR3","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1016\/j.comgeo.2006.01.002","volume":"36","author":"G Alexandron","year":"2007","unstructured":"Alexandron, G., Kaplan, H., Sharir, M.: Kinetic and dynamic data structures for convex hulls and upper envelopes. Comput. Geom. 36(2), 144\u20131158 (2007)","journal-title":"Comput. Geom."},{"key":"873_CR4","doi-asserted-by":"crossref","unstructured":"Bahrdt, D., Becher, M., Funke, S., Krumpe, F., Nusser, A., Seybold, M., Storandt, S.: Growing Balls in $${R}^d$$. In: Proceedings of the 19th Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 247\u2013258. SIAM (2017)","DOI":"10.1137\/1.9781611974768.20"},{"key":"873_CR5","doi-asserted-by":"crossref","unstructured":"Castermans, T., Speckmann, B., Staals, F., Verbeek, K.: Agglomerative clustering of growing squares. In: Latin American Symposium on Theoretical Informatics, pp. 260\u2013274. Springer (2018)","DOI":"10.1007\/978-3-319-77404-6_20"},{"key":"873_CR6","unstructured":"Castermans, T.H.A., Speckmann, B., Verbeek, K.A.B., Westenberg, M.A., Betti, A., van\u00a0den Berg, H.: GlamMap: Geovisualization for e-Humanities. In: Workshop on Visualization for the Digital Humanities (Vis4DH) (2016)"},{"key":"873_CR7","doi-asserted-by":"crossref","unstructured":"Funke, S., Krumpe, F., Storandt, S.: Crushing disks efficiently. In: International Workshop on Combinatorial Algorithms (IWOCA), pp. 43\u201354. Springer (2016)","DOI":"10.1007\/978-3-319-44543-4_4"},{"key":"873_CR8","unstructured":"Funke, S., Storandt, S.: Parametrized runtimes for ball tournaments. In: European Workshop on Computational Geometry (EuroCG), pp. 221\u2013224 (2017)"},{"key":"873_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-69672-5","volume-title":"Data Structures and Algorithms 1: Sorting and Searching","author":"K Mehlhorn","year":"1984","unstructured":"Mehlhorn, K.: Data Structures and Algorithms 1: Sorting and Searching. Springer, Berlin (1984)"},{"issue":"1","key":"873_CR10","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1137\/0202005","volume":"2","author":"J Nievergelt","year":"1973","unstructured":"Nievergelt, J., Reingold, E.M.: Binary Search Trees of Bounded Balance. SIAM J. Comput. (SICOMP) 2(1), 33\u201343 (1973)","journal-title":"SIAM J. Comput. (SICOMP)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00873-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00873-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00873-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,24]],"date-time":"2022-01-24T14:08:33Z","timestamp":1643033313000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00873-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,20]]},"references-count":10,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1]]}},"alternative-id":["873"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00873-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2021,11,20]]},"assertion":[{"value":"16 May 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 August 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 November 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}