{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,19]],"date-time":"2025-12-19T21:11:22Z","timestamp":1766178682303,"version":"3.41.0"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2025,2,13]],"date-time":"2025-02-13T00:00:00Z","timestamp":1739404800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) \u2013 Projektnummer","award":["459420781"],"award-info":[{"award-number":["459420781"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Spatial Algorithms Syst."],"published-print":{"date-parts":[[2025,3,31]]},"abstract":"<jats:p>An important task of pattern recognition and map generalization is to partition a set of disjoint polygons into groups and to aggregate the polygons within each group to a representative output polygon. We introduce a new method for this task called bicriteria shapes. Following a classical approach, we define the output polygons by merging the input polygons with a set of triangles that we select from a conforming Delaunay triangulation of the input polygons\u2019 exterior. The innovation is that we control the selection of triangles with a bicriteria optimization model that is efficiently solved via graph cuts. In particular, we minimize a weighted sum that combines the total area of the output polygons and their total perimeter. In a basic problem, we ask for a single solution that is optimal for a preset parameter value. In a second problem, we ask for a set containing an optimal solution for every possible value of the parameter. We discuss how this set can be approximated with few solutions and show that it is hierarchically nested. Hence, the output is a hierarchical clustering that corresponds to multiple levels of detail. An evaluation with building footprints as input and a comparison with \u03b1-shapes that are based on the same underlying triangulation conclude the article. An advantage of bicriteria shapes compared to \u03b1-shapes is that the sequence of solutions for decreasing values of the parameter is monotone with respect to the total perimeter of the output polygons, resulting in a monotonically decreasing visual complexity.<\/jats:p>","DOI":"10.1145\/3705001","type":"journal-article","created":{"date-parts":[[2024,12,3]],"date-time":"2024-12-03T11:00:02Z","timestamp":1733223602000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Bicriteria Shapes: Hierarchical Grouping and Aggregation of Polygons with an Efficient Graph-Cut Approach"],"prefix":"10.1145","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3926-4938","authenticated-orcid":false,"given":"Peter","family":"Rottmann","sequence":"first","affiliation":[{"name":"Institute of Geodesy and Geoinformation, Rheinische Friedrich-Wilhelms-Universit\u00e4t Bonn, Bonn, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1943-2589","authenticated-orcid":false,"given":"Anne","family":"Driemel","sequence":"additional","affiliation":[{"name":"Hausdorff Center for Mathematics, Rheinische Friedrich-Wilhelms-Universit\u00e4t Bonn, Bonn, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-2549-9622","authenticated-orcid":false,"given":"Herman","family":"Haverkort","sequence":"additional","affiliation":[{"name":"Institute of Computer Science, Rheinische Friedrich-Wilhelms-Universit\u00e4t Bonn, Bonn, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-8438-3986","authenticated-orcid":false,"given":"Heiko","family":"R\u00f6glin","sequence":"additional","affiliation":[{"name":"Institute of Computer Science, Rheinische Friedrich-Wilhelms-Universit\u00e4t Bonn, Bonn, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8005-943X","authenticated-orcid":false,"given":"Jan-Henrik","family":"Haunert","sequence":"additional","affiliation":[{"name":"Institute of Geodesy and Geoinformation, Rheinische Friedrich-Wilhelms-Universit\u00e4t Bonn, Bonn, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,2,13]]},"reference":[{"key":"e_1_3_3_2_2","series-title":"International Archives of Photogrammetry and Remote Sensing","first-page":"75","volume-title":"Proceedings of the 19th ISPRS Congress","volume":"33","author":"Anders Karl-Heinrich","year":"2000","unstructured":"Karl-Heinrich Anders and Monika Sester. 2000. Parameter-free cluster detection in spatial databases and its application to typification. In Proceedings of the 19th ISPRS Congress(International Archives of Photogrammetry and Remote Sensing, Vol. 33). 75\u201383."},{"key":"e_1_3_3_3_2","article-title":"Ausleitung des ATKIS-Objektartenkataloges DLM250","author":"(AdV) Arbeitsgemeinschaft der Vermessungsverwaltungen der L\u00e4nder der Bundesrepublik Deutschland","year":"2022","unstructured":"Arbeitsgemeinschaft der Vermessungsverwaltungen der L\u00e4nder der Bundesrepublik Deutschland (AdV). 2022. Ausleitung des ATKIS-Objektartenkataloges DLM250. Katalogwerke zur GeoInfoDok (2022). https:\/\/www.adv-online.de\/icc\/extdeu\/nav\/35b\/binarywriterservlet?imgUid=a8130147-1420-4e71-0832-12914a39df1f&uBasVariant=11111111-1111-1111-1111-111111111111","journal-title":"Katalogwerke zur GeoInfoDok"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.image.2006.11.012"},{"key":"e_1_3_3_5_2","first-page":"288","volume-title":"Proceedings of the 23rd Annual European Symposium on Algorithms","author":"B\u00f6kler Fritz","year":"2015","unstructured":"Fritz B\u00f6kler and Petra Mutzel. 2015. Output-sensitive algorithms for enumerating the extreme nondominated points of multiobjective combinatorial optimization problems. In Proceedings of the 23rd Annual European Symposium on Algorithms. Springer, 288\u2013299. DOI:DOI:10.1007\/978-3-662-48350-3_25"},{"key":"e_1_3_3_6_2","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1145\/3347146.3359087","volume-title":"Proceedings of the 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems","author":"Bonerath Annika","year":"2019","unstructured":"Annika Bonerath, Benjamin Niedermann, and Jan-Henrik Haunert. 2019. Retrieving \u03b1-shapes and schematic polygonal approximations for sets of points within queried temporal ranges. In Proceedings of the 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. 249\u2013258. DOI:DOI:10.1145\/3347146.3359087"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/0-387-28831-7_5"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1080\/13658810600912323"},{"key":"e_1_3_3_9_2","volume-title":"Proceedings of the 11th ICA Workshop on Generalisation and Multiple Representation","author":"Burghardt Dirk","year":"2007","unstructured":"Dirk Burghardt, Stefan Schmid, and Jantien Stoter. 2007. Investigations on cartographic constraint formalisation. In Proceedings of the 11th ICA Workshop on Generalisation and Multiple Representation. Retrieved from https:\/\/kartographie.geo.tu-dresden.de\/downloads\/ica-gen\/workshop2007\/Burghardt-ICAWorkshop.pdf"},{"key":"e_1_3_3_10_2","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1145\/2666310.2666414","volume-title":"Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems","author":"Chimani Markus","year":"2014","unstructured":"Markus Chimani, Thomas C. van Dijk, and Jan-Henrik Haunert. 2014. How to eat a graph: Computing selection sequences for the continuous generalization of road networks. In Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. Association for Computing Machinery, New York, NY, USA, 243\u2013252. DOI:DOI:10.1145\/2666310.2666414"},{"key":"e_1_3_3_11_2","volume-title":"Multiobjective Programming and Planning","author":"Cohon Jared L.","year":"1978","unstructured":"Jared L. Cohon. 1978. Multiobjective Programming and Planning. Academic Press, New York, NY, USA."},{"key":"e_1_3_3_12_2","first-page":"1","volume-title":"Proceedings of the 11th ICA Workshop on Generalisation and Multiple Representation","author":"Damen Jonathan","year":"2008","unstructured":"Jonathan Damen, Marc van Kreveld, and Bert Spaan. 2008. High quality building generalization by extending the morphological operators. In Proceedings of the 11th ICA Workshop on Generalisation and Multiple Representation. 1\u201312. Retrieved from https:\/\/kartographie.geo.tu-dresden.de\/downloads\/ica-gen\/workshop2008\/04_Damen_et_al.pdf"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0305-0548(01)00056-9"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/13093875X"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2008.03.023"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1983.1056714"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.3390\/ijgi8060258"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.5167\/uzh-163108"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1080\/15230406.2020.1851613"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/48014.61051"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1080\/13658810903401008"},{"key":"e_1_3_3_22_2","first-page":"373","volume-title":"Proceedings of the 21st Congress of the International Society for Photogrammetry and Remote Sensing","author":"Haunert Jan-Henrik","year":"2008","unstructured":"Jan-Henrik Haunert and Alexander Wolff. 2008. Optimal simplification of building ground plans. In Proceedings of the 21st Congress of the International Society for Photogrammetry and Remote Sensing. International Society of Photogrammetry and Remote Sensing, 373\u2013378."},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.3390\/ijgi6070218"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1559\/152304095782540221"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1080\/13658816.2015.1031671"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.3390\/ijgi7060204"},{"key":"e_1_3_3_27_2","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1109\/PIC.2010.5687417","volume-title":"Proceedings of the 2010 IEEE International Conference on Progress in Informatics and Computing","volume":"1","author":"Li Jingzhong","year":"2010","unstructured":"Jingzhong Li and Tinghua Ai. 2010. A triangulated spatial model for detection of spatial characteristics of GIS data. In Proceedings of the 2010 IEEE International Conference on Progress in Informatics and Computing, Vol. 1. 155\u2013159. DOI:DOI:10.1109\/PIC.2010.5687417"},{"key":"e_1_3_3_28_2","first-page":"355","volume-title":"Proceedings of the 12th International Conference on Advances in Practical Applications of Heterogeneous Multi-Agent Systems","author":"Maudet Adrien","year":"2014","unstructured":"Adrien Maudet, Guillaume Touya, C\u00e9cile Duch\u00eane, and S\u00e9bastien Picault. 2014. Multi-agent multi-level cartographic generalisation in CartAGen. In Proceedings of the 12th International Conference on Advances in Practical Applications of Heterogeneous Multi-Agent Systems. 355\u2013358. DOI:DOI:10.1007\/978-3-319-07551-8_37"},{"key":"e_1_3_3_29_2","volume-title":"Generalization in digital cartography","author":"McMaster Robert B.","year":"1992","unstructured":"Robert B. McMaster and K. Stuart Shea. 1992. Generalization in digital cartography. Association of American Geographers, Washington, DC, USA."},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3381449"},{"key":"e_1_3_3_31_2","first-page":"61","volume-title":"Proceedings of the 2nd International Conference on Computer Graphics Theory and Applications","author":"Moreira Adriano","year":"2007","unstructured":"Adriano Moreira and Maribel Y. Santos. 2007. Concave hull: A k-nearest neighbours approach for the computation of the region occupied by a set of points. In Proceedings of the 2nd International Conference on Computer Graphics Theory and Applications. 61\u201368. Retrieved from http:\/\/hdl.handle.net\/1822\/6429"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.compenvurbsys.2008.06.004"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.5311\/JOSIS.2017.15.379"},{"key":"e_1_3_3_34_2","article-title":"P","author":"contributors OpenStreetMap","year":"2020","unstructured":"OpenStreetMap contributors. 2020. Planet Dump Retrieved from https:\/\/planet.osm.org. Retrieved from https:\/\/www.openstreetmap.org","journal-title":"R"},{"key":"e_1_3_3_35_2","first-page":"765","volume-title":"Proceedings of the 45th Annual ACM Symposium on Theory of Computing","author":"Orlin James B.","year":"2013","unstructured":"James B. Orlin. 2013. Max flows in \\({O}(nm)\\) time, or better. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing. 765\u2013774. DOI:DOI:10.1145\/2488608.2488705"},{"key":"e_1_3_3_36_2","first-page":"16.1\u201316.10","volume-title":"Proceedings of the British Machine Vision Conference","author":"Peng Bo","year":"2008","unstructured":"Bo Peng and Olga Veksler. 2008. Parameter selection for graph cut based image segmentation. In Proceedings of the British Machine Vision Conference. 16.1\u201316.10. DOI:DOI:10.5244\/C.22.16"},{"key":"e_1_3_3_37_2","volume-title":"Proceedings of the 3rd ACM SIGSPATIAL Workshop on Smart Cities and Urban Analytics","author":"Peng Dongliang","year":"2017","unstructured":"Dongliang Peng and Guillaume Touya. 2017. Continuously generalizing buildings to built-up areas by aggregating and growing. In Proceedings of the 3rd ACM SIGSPATIAL Workshop on Smart Cities and Urban Analytics. Association for Computing Machinery, New York, NY, USA, Article 10, 8 pages. DOI:DOI:10.1145\/3152178.3152188"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/3409290"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1201\/9781420069273.ch16"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1090.0342"},{"key":"e_1_3_3_41_2","volume-title":"Spatial databases: with application to GIS","author":"Rigaux Phillipe","year":"2002","unstructured":"Phillipe Rigaux, Michel Scholl, and Agn\u00e9s Voisard. 2002. Spatial databases: with application to GIS. Morgan Kaufmann, San Francisco."},{"key":"e_1_3_3_42_2","first-page":"2007","volume-title":"Proceedings of the 5th International Conference on Geographic Information Science","author":"Roth Robert. E.","year":"2008","unstructured":"Robert. E. Roth, Michael Stryker, and Cynthia A. Brewer. 2008. A typology of multi-scale mapping operators. In Proceedings of the 5th International Conference on Geographic Information Science. 2007\u20132007."},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1080\/10106049.2020.1730449"},{"key":"e_1_3_3_44_2","volume-title":"Proceedings of the 16th ICA Generalisation Workshop","author":"Schwartges Nadine","year":"2013","unstructured":"Nadine Schwartges, Dennis Allerkamp, Jan-Henrik Haunert, and Alexander Wolff. 2013. Optimizing active ranges for point selection in dynamic maps. In Proceedings of the 16th ICA Generalisation Workshop."},{"key":"e_1_3_3_45_2","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1007\/978-3-642-10520-3_20","volume-title":"Proceedings of the 5th International Symposium on Advances in Visual Computing","author":"Sedlacek David","year":"2009","unstructured":"David Sedlacek and Jiri Zara. 2009. Graph cut based point-cloud segmentation for polygonal reconstruction. In Proceedings of the 5th International Symposium on Advances in Visual Computing. 218\u2013227. DOI:DOI:10.1007\/978-3-642-10520-3_20"},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009705404707"},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-26772-7_27"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1109\/34.868688"},{"key":"e_1_3_3_49_2","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1145\/1183471.1183484","volume-title":"Proceedings of the 14th Annual ACM International Symposium on Advances in Geographic Information Systems","author":"Steiniger Stefan","year":"2006","unstructured":"Stefan Steiniger, Dirk Burghardt, and Robert Weibel. 2006. Recognition of island structures for map generalization. In Proceedings of the 14th Annual ACM International Symposium on Advances in Geographic Information Systems. 67\u201374. DOI:DOI:10.1145\/1183471.1183484"},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.7480\/abe.2017.18"},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-03611-3_16"},{"key":"e_1_3_3_52_2","first-page":"1389","volume-title":"Proceedings of the 17th International Cartographic Conference","author":"Timpf Sabine","year":"1995","unstructured":"Sabine Timpf and Andrew U. Frank. 1995. A multi-scale data structure for cartographic objects. In Proceedings of the 17th International Cartographic Conference. 1389\u20131396."},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.1080\/23729333.2019.1613071"},{"key":"e_1_3_3_54_2","doi-asserted-by":"publisher","DOI":"10.1119\/1.14057"},{"key":"e_1_3_3_55_2","first-page":"2180","volume-title":"Proceedings of the 20th Intl. Geographic Conference","author":"Kreveld Marc Van","year":"2001","unstructured":"Marc Van Kreveld. 2001. Smooth generalization for continuous zooming. In Proceedings of the 20th Intl. Geographic Conference. 2180\u20132185."},{"key":"e_1_3_3_56_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-00203-3_4"},{"key":"e_1_3_3_57_2","doi-asserted-by":"publisher","DOI":"10.1109\/34.244673"},{"key":"e_1_3_3_58_2","doi-asserted-by":"publisher","DOI":"10.3390\/ijgi9040250"}],"container-title":["ACM Transactions on Spatial Algorithms and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3705001","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3705001","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:18:02Z","timestamp":1750295882000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3705001"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,13]]},"references-count":57,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,3,31]]}},"alternative-id":["10.1145\/3705001"],"URL":"https:\/\/doi.org\/10.1145\/3705001","relation":{},"ISSN":["2374-0353","2374-0361"],"issn-type":[{"type":"print","value":"2374-0353"},{"type":"electronic","value":"2374-0361"}],"subject":[],"published":{"date-parts":[[2025,2,13]]},"assertion":[{"value":"2023-03-18","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-08","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-02-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}