{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T13:08:42Z","timestamp":1776690522026,"version":"3.51.2"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2016,4,8]],"date-time":"2016-04-08T00:00:00Z","timestamp":1460073600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Netherlands Organisation for Scientific Research","doi-asserted-by":"crossref","award":["612.001.207, 639.022.707 and 639.023.208"],"award-info":[{"award-number":["612.001.207, 639.022.707 and 639.023.208"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"crossref"}]},{"name":"NSERC and Carleton University\u2019s President\u2019s 2010 Doctoral Fellowship"},{"DOI":"10.13039\/501100009024","name":"JST, ERATO, Kawarabayashi Large Graph Project","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100009024","id-type":"DOI","asserted-by":"publisher"}]},{"name":"EU Horizon 2020 programme, under a Marie Sk\u0142odowska-Curie Individual Fellowship","award":["656741"],"award-info":[{"award-number":["656741"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Spatial Algorithms Syst."],"published-print":{"date-parts":[[2016,4,8]]},"abstract":"<jats:p>\n            In this article, we study automated simplification and schematization of territorial outlines. We present a quadratic-time simplification algorithm based on an operation called\n            <jats:italic>edge-move<\/jats:italic>\n            . We prove that the number of edges of any nonconvex simple polygon can be reduced with this operation. Moreover, edge-moves preserve area and topology and do not introduce new orientations. The latter property in particular makes the algorithm highly suitable for schematization in which all resulting lines are required to be parallel to one of a given set of lines (orientations). To obtain such a result, we need only to preprocess the input to use only lines that are parallel to one of the given set. We present an algorithm to enforce such orientation restrictions, again without changing area or topology. Experiments show that our algorithms obtain results of high visual quality.\n          <\/jats:p>","DOI":"10.1145\/2818373","type":"journal-article","created":{"date-parts":[[2016,5,21]],"date-time":"2016-05-21T22:27:38Z","timestamp":1463869658000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":30,"title":["Area-Preserving Simplification and Schematization of Polygonal Subdivisions"],"prefix":"10.1145","volume":"2","author":[{"given":"Kevin","family":"Buchin","sequence":"first","affiliation":[{"name":"TU Eindhoven, MB Eindhoven, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wouter","family":"Meulemans","sequence":"additional","affiliation":[{"name":"City University London, London, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andr\u00e9 Van","family":"Renssen","sequence":"additional","affiliation":[{"name":"National Institute of Informatics, Tokyo, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bettina","family":"Speckmann","sequence":"additional","affiliation":[{"name":"TU Eindhoven, MB Eindhoven, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,4,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2014.02.002"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.75509"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/645973.675364"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1559\/152304098782383007"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2005.06.008"},{"key":"e_1_2_1_6_1","volume-title":"Abstracts of the 27th European Workshop on Computational Geometry. 163--166","author":"Buchin K.","unstructured":"K. Buchin , W. Meulemans , and B. Speckmann . 2011a. Area-preserving C-oriented schematization . In Abstracts of the 27th European Workshop on Computational Geometry. 163--166 . K. Buchin, W. Meulemans, and B. Speckmann. 2011a. Area-preserving C-oriented schematization. In Abstracts of the 27th European Workshop on Computational Geometry. 163--166."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2093973.2094009"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.11.002"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1810959.1810962"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31125-3_21"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.gmod.2012.04.006"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13731-0_27"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2525314.2525452"},{"key":"e_1_2_1_15_1","volume-title":"Geographic Information Science. Lecture Notes in Computer Science","volume":"8728","author":"van Dijk T. C.","unstructured":"T. C. van Dijk , A. van Goethem , J.-H. Haunert , W. Meulemans , and B. Speckmann . 2014. Map schematization with circular arcs . In Geographic Information Science. Lecture Notes in Computer Science , Vol. 8728 . Springer, 1--17. T. C. van Dijk, A. van Goethem, J.-H. Haunert, W. Meulemans, and B. Speckmann. 2014. Map schematization with circular arcs. In Geographic Information Science. Lecture Notes in Computer Science, Vol. 8728. Springer, 1--17."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.3138\/FM57-6770-U75U-7727"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/378583.378612"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36763-2_41"},{"key":"e_1_2_1_19_1","volume-title":"SOFSEM 2011: Theory and Practice of Computer Science. Lecture Notes in Computer Science","volume":"6543","author":"Gemsa A.","unstructured":"A. Gemsa , M. N\u00f6llenburg , T. Pajor , and I. Rutter . 2011. On d-regular schematization of embedded paths . In SOFSEM 2011: Theory and Practice of Computer Science. Lecture Notes in Computer Science , Vol. 6543 . Springer, 260--271. A. Gemsa, M. N\u00f6llenburg, T. Pajor, and I. Rutter. 2011. On d-regular schematization of embedded paths. In SOFSEM 2011: Theory and Practice of Computer Science. Lecture Notes in Computer Science, Vol. 6543. Springer, 260--271."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1179\/1743277413Y.0000000066"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/PacificVis.2014.11"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195993000257"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.isprsjprs.2012.08.004"},{"key":"e_1_2_1_24_1","first-page":"71","article-title":"Polygonal approximations of a curve\u2014formulations and algorithms","volume":"6","author":"Imai H.","year":"1988","unstructured":"H. Imai and M. Iri . 1988 . Polygonal approximations of a curve\u2014formulations and algorithms . Computational Morphology 6 , 71 -- 86 . H. Imai and M. Iri. 1988. Polygonal approximations of a curve\u2014formulations and algorithms. Computational Morphology 6, 71--86.","journal-title":"Computational Morphology"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/220279.220336"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/11552499_71"},{"key":"e_1_2_1_27_1","volume-title":"Graph Drawing. Lecture Notes in Computer Science","volume":"4372","author":"Merrick D.","unstructured":"D. Merrick and J. Gudmundsson . 2006. Path simplification for metro map layout . In Graph Drawing. Lecture Notes in Computer Science , Vol. 4372 . Springer, 258--269. D. Merrick and J. Gudmundsson. 2006. Path simplification for metro map layout. In Graph Drawing. Lecture Notes in Computer Science, Vol. 4372. Springer, 258--269."},{"key":"e_1_2_1_29_1","volume-title":"Geographic Information Science. Lecture Notes in Computer Science","volume":"6292","author":"Meulemans W.","unstructured":"W. Meulemans , A. van Renssen , and B. Speckmann . 2010. Area-preserving subdivision schematization . In Geographic Information Science. Lecture Notes in Computer Science , Vol. 6292 . Springer, 160--74. W. Meulemans, A. van Renssen, and B. Speckmann. 2010. Area-preserving subdivision schematization. In Geographic Information Science. Lecture Notes in Computer Science, Vol. 6292. Springer, 160--74."},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 7th IEEE International Conference on Computer Vision. 108--115","author":"Munich M. E.","unstructured":"M. E. Munich and P. Perona . 1999. Continuous dynamic time warping for translation-invariant curve alignment with applications to signature verification . In Proceedings of the 7th IEEE International Conference on Computer Vision. 108--115 . M. E. Munich and P. Perona. 1999. Continuous dynamic time warping for translation-invariant curve alignment with applications to signature verification. In Proceedings of the 7th IEEE International Conference on Computer Vision. 108--115."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/378583.378614"},{"key":"e_1_2_1_32_1","series-title":"Lecture Notes in Computer Science","volume-title":"Algorithms and Data Structures","author":"Neyer G.","unstructured":"G. Neyer . 1999. Line simplification with restricted orientations . In Algorithms and Data Structures . Lecture Notes in Computer Science , Vol. 1663 . Springer , 13--24. G. Neyer. 1999. Line simplification with restricted orientations. In Algorithms and Data Structures. Lecture Notes in Computer Science, Vol. 1663. Springer, 13--24."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2010.81"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1080\/13658810210149434"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the ICA\u201999 Workshop on Progress in Automated Map Generalization.","author":"Regnauld N.","unstructured":"N. Regnauld , A. Edwardes , and M. Barrault . 1999. Strategies in building generalisation: Modelling the sequence, constraining the choice . In Proceedings of the ICA\u201999 Workshop on Progress in Automated Map Generalization. N. Regnauld, A. Edwardes, and M. Barrault. 1999. Strategies in building generalisation: Modelling the sequence, constraining the choice. In Proceedings of the ICA\u201999 Workshop on Progress in Automated Map Generalization."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1179\/000870410X12825500202896"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 14th ICA Workshop on Generalisation and Multiple Representation.","author":"Reimer A.","unstructured":"A. Reimer and W. Meulemans . 2011. Parallelity in chorematic territorial outlines . In Proceedings of the 14th ICA Workshop on Generalisation and Multiple Representation. A. Reimer and W. Meulemans. 2011. Parallelity in chorematic territorial outlines. In Proceedings of the 14th ICA Workshop on Generalisation and Multiple Representation."},{"key":"e_1_2_1_38_1","unstructured":"M. J. Roberts. 2012. Underground Maps Unravelled\u2014Explorations in Information Design. Self-Published.  M. J. Roberts. 2012. Underground Maps Unravelled\u2014Explorations in Information Design. Self-Published."},{"key":"e_1_2_1_39_1","volume-title":"Web and Wireless Geographical Information Systems. Lecture Notes in Computer Science","volume":"4857","author":"Swan J.","unstructured":"J. Swan , S. Anand , M. Ware , and M. Jackson . 2007. Automated schematization for Web service applications . In Web and Wireless Geographical Information Systems. Lecture Notes in Computer Science , Vol. 4857 . Springer, 216--226. J. Swan, S. Anand, M. Ware, and M. Jackson. 2007. Automated schematization for Web service applications. In Web and Wireless Geographical Information Systems. Lecture Notes in Computer Science, Vol. 4857. Springer, 216--226."},{"key":"e_1_2_1_40_1","first-page":"84","article-title":"Area preserving cartographic line generalization","volume":"8","author":"Tuti\u0107 D.","year":"2009","unstructured":"D. Tuti\u0107 and M. Lapaine . 2009 . Area preserving cartographic line generalization . Cartography and Geoinformation 8 , 11, 84 -- 100 . D. Tuti\u0107 and M. Lapaine. 2009. Area preserving cartographic line generalization. Cartography and Geoinformation 8, 11, 84--100.","journal-title":"Cartography and Geoinformation"},{"key":"e_1_2_1_41_1","series-title":"Lecture Notes in Computer Science","volume-title":"Spatial Information Theory: A Theoretical Basis for GIS","author":"Tversky B.","unstructured":"B. Tversky . 1993. Cognitive maps, cognitive collages, and spatial mental models . In Spatial Information Theory: A Theoretical Basis for GIS . Lecture Notes in Computer Science , Vol. 716 . Springer , 14--24. B. Tversky. 1993. Cognitive maps, cognitive collages, and spatial mental models. In Spatial Information Theory: A Theoretical Basis for GIS. Lecture Notes in Computer Science, Vol. 716. Springer, 14--24."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1179\/caj.1993.30.1.46"}],"container-title":["ACM Transactions on Spatial Algorithms and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2818373","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2818373","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:43:39Z","timestamp":1750225419000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2818373"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,4,8]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,4,8]]}},"alternative-id":["10.1145\/2818373"],"URL":"https:\/\/doi.org\/10.1145\/2818373","relation":{},"ISSN":["2374-0353","2374-0361"],"issn-type":[{"value":"2374-0353","type":"print"},{"value":"2374-0361","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,4,8]]},"assertion":[{"value":"2013-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-04-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}