{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:10:44Z","timestamp":1740143444535,"version":"3.37.3"},"reference-count":14,"publisher":"Association for Computing Machinery (ACM)","funder":[{"name":"DFG","award":["FE407\/21-1"]},{"name":"Computational Geometry: Solving Hard Optimization Problems"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"\n We consider methods for finding a simple polygon of minimum (\n Min-Area<\/jats:sc>\n ) or maximum (\n Max-Area<\/jats:sc>\n ) possible area for a given set of points in the plane. Both problems are known to be NP-hard; at the center of the recent CG Challenge, practical methods have received considerable attention. However, previous methods focused on heuristic methods, with no proof of optimality. We develop exact methods, based on a combination of geometry and integer programming. As a result, we are able to solve instances of up to\n \n \\( n=25 \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n points to provable optimality. While this extends the range of solvable instances by a considerable amount, it also illustrates the practical difficulty of both problem variants.\n <\/jats:p>","DOI":"10.1145\/3503607","type":"journal-article","created":{"date-parts":[[2022,5,25]],"date-time":"2022-05-25T09:02:26Z","timestamp":1653469346000},"page":"1-23","source":"Crossref","is-referenced-by-count":2,"title":["Computing Area-Optimal Simple Polygonizations"],"prefix":"10.1145","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9062-4241","authenticated-orcid":false,"given":"S\u00e1ndor P.","family":"Fekete","sequence":"first","affiliation":[{"name":"Department of Computer Science, TU Braunschweig, Braunschweig, Germany"}]},{"given":"Andreas","family":"Haas","sequence":"additional","affiliation":[{"name":"Department of Computer Science, TU Braunschweig, Braunschweig, Germany"}]},{"given":"Phillip","family":"Keldenich","sequence":"additional","affiliation":[{"name":"Department of Computer Science, TU Braunschweig, Braunschweig, Germany"}]},{"given":"Michael","family":"Perk","sequence":"additional","affiliation":[{"name":"Department of Computer Science, TU Braunschweig, Braunschweig, Germany"}]},{"given":"Arne","family":"Schmidt","sequence":"additional","affiliation":[{"name":"Department of Computer Science, TU Braunschweig, Braunschweig, Germany"}]}],"member":"320","published-online":{"date-parts":[[2022,5,25]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3504000"},{"key":"e_1_3_1_3_2","volume-title":"Geometry and the Travelling Salesman Problem","author":"Fekete S\u00e1ndor P.","year":"1992","unstructured":"S\u00e1ndor P. Fekete. 1992. Geometry and the Travelling Salesman Problem. Ph.D. Thesis. Department of Combinatorics and Optimization, University of Waterloo, Waterloo, ON."},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009492"},{"key":"e_1_3_1_5_2","first-page":"133","volume-title":"Proceedings of the European Workshop on Computational Geometry","author":"Fekete S\u00e1ndor P.","year":"2015","unstructured":"S\u00e1ndor P. Fekete, Stephan Friedrichs, Michael Hemmer, Melanie Papenberg, Arne Schmidt, and Julian Troegel. 2015. Area-and boundary-optimal polygonalization of planar point sets. In Proceedings of the European Workshop on Computational Geometry. 133\u2013136."},{"key":"e_1_3_1_6_2","first-page":"29:1\u201329:9","volume-title":"Proceedings of the European Workshop on Computational Geometry","author":"Fekete S\u00e1ndor P.","year":"2020","unstructured":"S\u00e1ndor P. Fekete, Andreas Haas, Dominik Krupke, Yannic Lieder, Eike Niehs, Michael Perk, Victoria Sack, and Christian Scheffer. 2020. Hard instances of the minimum-weight triangulation problem. In Proceedings of the European Workshop on Computational Geometry. 29:1\u201329:9."},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/160985.161016"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/0109047"},{"key":"e_1_3_1_10_2","first-page":"44:1\u201344:14","volume-title":"Proceedings of the Symposium on Computational Geometry","author":"Haas Andreas","year":"2018","unstructured":"Andreas Haas. 2018. Solving large-scale minimum-weight triangulation instances to provable optimality. In Proceedings of the Symposium on Computational Geometry. 44:1\u201344:14."},{"key":"e_1_3_1_11_2","volume-title":"Exact Methods for Area-Optimal Polygons","author":"Papenberg Melanie","year":"2014","unstructured":"Melanie Papenberg. 2014. Exact Methods for Area-Optimal Polygons. Master\u2019s thesis. Braunschweig University of Technology."},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1115\/1.4029559"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/2896849"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263872"},{"key":"e_1_3_1_15_2","first-page":"161","volume-title":"Proceedings of the Congreso Argentino de Ciencias de la Computaci\u00f3n (CACIC)","author":"Taranilla Maria Teresa","year":"2011","unstructured":"Maria Teresa Taranilla, Edilma Olinda Gagliardi, and Gregorio Hern\u00e1ndez Pe\u00f1alver. 2011. Approaching minimum area polygonization. In Proceedings of the Congreso Argentino de Ciencias de la Computaci\u00f3n (CACIC). 161\u2013170."}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3503607","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,2]],"date-time":"2023-01-02T01:13:18Z","timestamp":1672621998000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3503607"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,25]]},"references-count":14,"alternative-id":["10.1145\/3503607"],"URL":"https:\/\/doi.org\/10.1145\/3503607","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2022,5,25]]}}}