{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,29]],"date-time":"2025-11-29T07:59:04Z","timestamp":1764403144155,"version":"3.41.0"},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2022,3,17]],"date-time":"2022-03-17T00:00:00Z","timestamp":1647475200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Austrian Science Fund","award":["ORD 53-VO and P31013-N31"],"award-info":[{"award-number":["ORD 53-VO and P31013-N31"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"<jats:p>\n            Our work on the Computational Geometry Challenge 2019 on area-optimal polygonizations is based on two key components: (1) sampling the search space to obtain initial polygonizations and (2) optimizing such a polygonizations. Among other heuristics for obtaining polygonizations for a given set\n            <jats:italic>P<\/jats:italic>\n            of input points, we discuss how to combine 2-opt moves with a line sweep to convert an initial random (non-simple) polygon whose vertices are given by\n            <jats:italic>P<\/jats:italic>\n            into a polygonization\n            <jats:monospace>P<\/jats:monospace>\n            . The actual optimization relies on a constrained triangulation of the interior and exterior of a polygonization to speed-up local modifications of the polygonization to increase or decrease its area.\n          <\/jats:p>","DOI":"10.1145\/3500913","type":"journal-article","created":{"date-parts":[[2022,3,17]],"date-time":"2022-03-17T11:10:50Z","timestamp":1647515450000},"page":"1-12","source":"Crossref","is-referenced-by-count":2,"title":["2-Opt Moves and Flips for Area-optimal Polygonizations"],"prefix":"10.1145","volume":"27","author":[{"given":"G\u00fcnther","family":"Eder","sequence":"first","affiliation":[{"name":"FB Computerwissenschaften, Universit\u00e4t Salzburg, Salzburg, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0728-7545","authenticated-orcid":false,"given":"Martin","family":"Held","sequence":"additional","affiliation":[{"name":"FB Computerwissenschaften, Universit\u00e4t Salzburg, Salzburg, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stein\u00fe\u00f3r","family":"Jasonarson","sequence":"additional","affiliation":[{"name":"FB Computerwissenschaften, Universit\u00e4t Salzburg, Salzburg, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Philipp","family":"Mayer","sequence":"additional","affiliation":[{"name":"FB Computerwissenschaften, Universit\u00e4t Salzburg, Salzburg, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Palfrader","sequence":"additional","affiliation":[{"name":"FB Computerwissenschaften, Universit\u00e4t Salzburg, Salzburg, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,3,17]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.5555\/648249.751880"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1979.1675432"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.6.6.791"},{"key":"e_1_3_2_5_2","article-title":"Greedy and local search solutions to the minimum and maximum area","author":"Crombez Lo\u00efc","year":"2021","unstructured":"Lo\u00efc Crombez, Guilherme D. da Fonseca, and Yan Gerard. 2021. Greedy and local search solutions to the minimum and maximum area. ACM J. Experimental Algorithmics (2021).","journal-title":"ACM J. Experimental Algorithmics"},{"key":"e_1_3_2_6_2","article-title":"Area-optimal simple polygonalizations: The CG challenge","author":"Demaine Erik D.","year":"2021","unstructured":"Erik D. Demaine, S\u00e1ndor P. Fekete, Phillip Keldenich, Dominik Krupke, and Joseph S.B. Mitchell. 2021. Area-optimal simple polygonalizations: The CG challenge. ACM J. Experimental Algorithmics (2021).","journal-title":"ACM J. Experimental Algorithmics"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dib.2020.105984"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(00)00010-9"},{"key":"e_1_3_2_9_2","doi-asserted-by":"crossref","unstructured":"Nir Goren Efi Fogel and Dan Halperin. 2021. Area-optimal polygonization using simulated annealing (unpublished).","DOI":"10.1145\/3500911"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0028-4"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(99)00284-2"},{"key":"e_1_3_2_12_2","article-title":"Optimal area polygonization by triangulation and ray-tracing","author":"Lepagnot Julien","year":"2021","unstructured":"Julien Lepagnot, Laurent Moalic, and Dominique Schmitt. 2021. Optimal area polygonization by triangulation and ray-tracing. ACM J. Experimental Algorithmics.","journal-title":"ACM J. Experimental Algorithmics"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.21.2.498"},{"key":"e_1_3_2_14_2","article-title":"Heuristics for area optimal polygonizations","author":"Ramos Natanael","year":"2021","unstructured":"Natanael Ramos, Ra\u00ed C. de Jesus, Pedro de Rezende, Cid de Souza, and F\u00e1bio L. Usberti. 2021. Heuristics for area optimal polygonizations. ACM J. Experimental Algorithmics (2021).","journal-title":"ACM J. Experimental Algorithmics"},{"key":"e_1_3_2_15_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1007\/BFb0014497","volume-title":"Applied Computational Geometry: Towards Geometric Engineering","author":"Shewchuk Jonathan R.","year":"1996","unstructured":"Jonathan R. Shewchuk. 1996. Triangle: Engineering a 2D quality mesh generator and delaunay triangulator. In Applied Computational Geometry: Towards Geometric Engineering. Lecture Notes in Computer Science, Vol. 1148. Springer-Verlag, 203\u2013222."},{"key":"e_1_3_2_16_2","first-page":"87","volume-title":"Proceedings of the 7th Conference Graph-theoretic Concepts in Computer Science (WG\u201981)","author":"Leeuwen Jan van","year":"1982","unstructured":"Jan van Leeuwen and Anneke A. Schoone. 1982. Untangling a travelling salesman tour in the plane. In Proceedings of the 7th Conference Graph-theoretic Concepts in Computer Science (WG\u201981), J. R. M\u00fchlbacher (Ed.). 87\u201398."},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00031-3"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3500913","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3500913","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:49:40Z","timestamp":1750182580000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3500913"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,17]]},"references-count":16,"alternative-id":["10.1145\/3500913"],"URL":"https:\/\/doi.org\/10.1145\/3500913","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2022,3,17]]}}}