{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,12]],"date-time":"2025-12-12T13:44:26Z","timestamp":1765547066967,"version":"3.41.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2023,8,16]],"date-time":"2023-08-16T00:00:00Z","timestamp":1692144000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Austrian Science Fund","award":["Y1329, and P31119"],"award-info":[{"award-number":["Y1329, and P31119"]}]},{"DOI":"10.13039\/501100001821","name":"Vienna Science and Technology Fund","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001821","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Spatial Algorithms Syst."],"published-print":{"date-parts":[[2023,9,30]]},"abstract":"<jats:p>\n            Point feature labeling is a classical problem in cartography and GIS that has been extensively studied for geospatial point data. At the same time, word clouds are a popular visualization tool to show the most important words in text data which has also been extended to visualize geospatial data (Buchin et\u00a0al. PacificVis 2016). In this article, we study a hybrid visualization, which combines aspects of word clouds and point labeling. In the considered setting, the input data consist of a set of points grouped into categories and our aim is to place multiple disjoint and axis-aligned rectangles, each representing a category, such that they cover points of (mostly) the same category under some natural quality constraints. In our visualization, we then place category names inside the computed rectangles to produce a labeling of the covered points which summarizes the predominant categories globally (in a word-cloud-like fashion) while locally avoiding excessive misrepresentation of points (i.e., retaining the precision of point labeling). We show that computing a minimum set of such rectangles is\n            <jats:sans-serif>NP<\/jats:sans-serif>\n            -hard. Hence, we turn our attention to developing a heuristic with (optional) exact components using\n            <jats:sans-serif>SAT<\/jats:sans-serif>\n            models to compute our visualizations. We evaluate our algorithms quantitatively, measuring running time and quality of the produced solutions, on several synthetic and real-world data sets. Our experiments show that the fully heuristic approach produces solutions of comparable quality to heuristics combined with exact\n            <jats:sans-serif>SAT<\/jats:sans-serif>\n            models, while running much faster.\n          <\/jats:p>","DOI":"10.1145\/3603376","type":"journal-article","created":{"date-parts":[[2023,6,9]],"date-time":"2023-06-09T12:00:11Z","timestamp":1686312011000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Worbel: Aggregating Point Labels into Word Clouds"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0104-1659","authenticated-orcid":false,"given":"Sujoy","family":"Bhore","sequence":"first","affiliation":[{"name":"Indian Institute of Technology Bombay, India"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7762-8045","authenticated-orcid":false,"given":"Robert","family":"Ganian","sequence":"additional","affiliation":[{"name":"Algorithms and Complexity Group, TU Wien, Austria"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7966-076X","authenticated-orcid":false,"given":"Guangping","family":"Li","sequence":"additional","affiliation":[{"name":"Algorithms and Complexity Group, TU Wien, Austria"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0454-3937","authenticated-orcid":false,"given":"Martin","family":"N\u00f6llenburg","sequence":"additional","affiliation":[{"name":"Algorithms and Complexity Group, TU Wien, Austria"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9314-8260","authenticated-orcid":false,"given":"Jules","family":"Wulms","sequence":"additional","affiliation":[{"name":"Algorithms and Complexity Group, TU Wien, Austria"}]}],"member":"320","published-online":{"date-parts":[[2023,8,16]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.50"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-019-00099-6"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(98)00028-5"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2010.10.002"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21398-9_43"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0216-x"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0198-9715(00)00039-9"},{"key":"e_1_3_2_9_2","first-page":"514","volume-title":"Proceedings of the 11th Latin American Symposium on Theoretical Informatics.","author":"Barth Lukas","year":"2014","unstructured":"Lukas Barth, Sara Irina Fabrikant, Stephen G. Kobourov, Anna Lubiw, Martin N\u00f6llenburg, Yoshio Okamoto, Sergey Pupyrev, Claudio Squarcella, Torsten Ueckerdt, and Alexander Wolff. 2014. Semantic word cloud representations: Hardness and approximation algorithms. In Proceedings of the 11th Latin American Symposium on Theoretical Informatics.Springer, 514\u2013525. DOI:https:\/\/doi.org\/10.1007\/978-3-642-54423-1_45"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2012.01.014"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2020.19"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/PACIFICVIS.2016.7465262"},{"key":"e_1_3_2_13_2","first-page":"345","volume-title":"Proceedings of the 11th Symposium on Discrete Algorithms","author":"Carr Robert D.","year":"2000","unstructured":"Robert D. Carr, Srinivas Doddi, Goran Konjevod, and Madhav V. Marathe. 2000. On the red-blue set cover problem. In Proceedings of the 11th Symposium on Discrete Algorithms. SIAM, 345\u2013353."},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.54"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2014.12.005"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2015.2440241"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-006-1273-8"},{"key":"e_1_3_2_18_2","unstructured":"Jessica Davies and Fahiem Bacchus. 2014. MaxHS. Retrieved May 28 2021 from http:\/\/maxhs.org\/."},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/060656048"},{"key":"e_1_3_2_20_2","volume-title":"Cartography: Thematic Map Design (6th ed.)","author":"Dent Borden D.","year":"2009","unstructured":"Borden D. Dent, Jeffrey S Torguson, and Thomas W. Hodler. 2009. Cartography: Thematic Map Design (6th ed.). McGraw-Hill."},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/109648.109680"},{"key":"e_1_3_2_22_2","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman."},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.3390\/ijgi6110342"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3347146.3359359"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.visinf.2018.04.006"},{"key":"e_1_3_2_26_2","first-page":"181","volume-title":"Proceedings of the Visual Analytics Science and Technology","author":"MacEachren Alan M.","year":"2011","unstructured":"Alan M. MacEachren, Anuj R. Jaiswal, Anthony C. Robinson, Scott Pezanowski, Alexander Savelyev, Prasenjit Mitra, Xiao Zhang, and Justine I. Blanford. 2011. SensePlace2: GeoTwitter analytics support for situational awareness. In Proceedings of the Visual Analytics Science and Technology. IEEE, 181\u2013190."},{"key":"e_1_3_2_27_2","volume-title":"The Computational Complexity of Cartographic Label Placement","author":"Marks Joe","year":"1991","unstructured":"Joe Marks and Stuart Shieber. 1991. The Computational Complexity of Cartographic Label Placement. Technical Report. Harvard University. Retrieved 10 March 2023 from http:\/\/www.eecs.harvard.edu\/shieber\/Biblio\/Papers\/label.pdf."},{"key":"e_1_3_2_28_2","first-page":"1","volume-title":"Proceedings of the Handbook on Graph Drawing and Visualization","author":"Patrignani Maurizio","year":"2013","unstructured":"Maurizio Patrignani. 2013. Planarity testing and embedding. In Proceedings of the Handbook on Graph Drawing and Visualization. Roberto Tamassia (Ed.), Chapman and Hall\/CRC, 1\u201342."},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2018.2816208"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/VISUAL.2019.8933654"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.3138\/carto.49.1.2137"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/IV.2007.71"},{"key":"e_1_3_2_33_2","volume-title":"Geometric Algorithms for Cartographic Label Placement","author":"Strijk Tycho","year":"2001","unstructured":"Tycho Strijk. 2001. Geometric Algorithms for Cartographic Label Placement. Ph. D. Dissertation. Universiteit Utrecht."},{"key":"e_1_3_2_34_2","first-page":"41","volume-title":"Proceedings of the Pacific Visualization","author":"Thom Dennis","year":"2012","unstructured":"Dennis Thom, Harald Bosch, Steffen Koch, Michael W\u00f6rner, and Thomas Ertl. 2012. Spatiotemporal anomaly detection through visual analysis of geolocated Twitter messages. In Proceedings of the Pacific Visualization. IEEE, 41\u201348."},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1981.6312176"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1201\/9781420035315.ch58"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(99)00005-X"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2009.171"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1179\/000870472787352505"}],"container-title":["ACM Transactions on Spatial Algorithms and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3603376","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3603376","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:25Z","timestamp":1750178785000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3603376"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,16]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,9,30]]}},"alternative-id":["10.1145\/3603376"],"URL":"https:\/\/doi.org\/10.1145\/3603376","relation":{},"ISSN":["2374-0353","2374-0361"],"issn-type":[{"type":"print","value":"2374-0353"},{"type":"electronic","value":"2374-0361"}],"subject":[],"published":{"date-parts":[[2023,8,16]]},"assertion":[{"value":"2022-07-29","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-05-16","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-08-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}