{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,29]],"date-time":"2025-11-29T07:58:59Z","timestamp":1764403139819,"version":"3.41.0"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2022,3,4]],"date-time":"2022-03-04T00:00:00Z","timestamp":1646352000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["1736\/19"],"award-info":[{"award-number":["1736\/19"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"name":"NSF\/US-Israel-BSF","award":["2019754"],"award-info":[{"award-number":["2019754"]}]},{"name":"Israel Ministry of Science and Technology","award":["103129"],"award-info":[{"award-number":["103129"]}]},{"name":"Blavatnik Computer Science Research Fund"},{"name":"Yandex Machine Learning Initiative for Machine Learning at Tel Aviv University"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"<jats:p>\n            We describe a practical method to find near-optimal solutions for the area-optimal simple polygonization problem: Given a set of points\n            <jats:italic>S<\/jats:italic>\n            in the plane, the objective is to find a simple polygon of minimum or maximum area defined by\n            <jats:italic>S<\/jats:italic>\n            . Our approach is based on the celebrated metaheuristic Simulated Annealing. The method consists of a modular pipeline of steps, where each step can be implemented in various ways and with several parameters controlling it. We have implemented several different algorithms and created an application that computes a polygon with minimal (or maximal) area. We experimented with the various algorithmic options and with the controlling parameters of each algorithm to tune up the pipeline. Then, we executed the application on each of the benchmark instances, exploiting a grid of servers, to obtain near optimal results.\n          <\/jats:p>","DOI":"10.1145\/3500911","type":"journal-article","created":{"date-parts":[[2022,3,4]],"date-time":"2022-03-04T10:43:30Z","timestamp":1646390610000},"page":"1-17","source":"Crossref","is-referenced-by-count":7,"title":["Area Optimal Polygonization Using Simulated Annealing"],"prefix":"10.1145","volume":"27","author":[{"given":"Nir","family":"Goren","sequence":"first","affiliation":[{"name":"The Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7228-8806","authenticated-orcid":false,"given":"Efi","family":"Fogel","sequence":"additional","affiliation":[{"name":"The Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3345-3765","authenticated-orcid":false,"given":"Dan","family":"Halperin","sequence":"additional","affiliation":[{"name":"The Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,3,4]]},"reference":[{"key":"e_1_3_2_2_2","volume-title":"CGAL User and Reference Manual (5.0.2 ed.)","author":"Br\u00f6nnimann Herv\u00e9","year":"2020","unstructured":"Herv\u00e9 Br\u00f6nnimann, Andreas Fabri, Geert-Jan Giezeman, Susan Hert, Michael Hoffmann, Lutz Kettner, Sylvain Pion, and Stefan Schirra. 2020. 2D and 3D linear geometry kernel. In CGAL User and Reference Manual (5.0.2 ed.). CGAL Editorial Board. https:\/\/doc.cgal.org\/latest\/Manual\/packages.html#PkgKernel23."},{"key":"e_1_3_2_3_2","article-title":"Greedy and local search solutions to the minimum and maximum area polygons","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 polygons. The ACM J. of Experimental Alg. (2021). to appear.","journal-title":"The ACM J. of Experimental Alg."},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-1507-4_13"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2"},{"key":"e_1_3_2_6_2","article-title":"Area-optimal simple polygonalizations: The CG challenge 2019","author":"Demain Erik D.","year":"2021","unstructured":"Erik D. Demain, S\u00e1ndor P. Fekete, Phillip Keldenich, Dominik Krupte, and Josepth S. Mitchell. 2021. Area-optimal simple polygonalizations: The CG challenge 2019. The ACM J. of Experimental Alg. (2021). to appear.","journal-title":"The ACM J. of Experimental Alg."},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8655(93)90141-y"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009492"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.5555\/2341087"},{"key":"e_1_3_2_10_2","unstructured":"The ACM J. of Experimental Alg. 2021 Natanael Ramos Ra\u00ed Caetano de Jesus Pedro J. de Rezende Cid C. de Souza and F\u00e1bio Luiz Usberti"},{"key":"e_1_3_2_11_2","volume-title":"Handbook of Metaheuristics","author":"Gendreau Michel","year":"2003","unstructured":"Michel Gendreau and Jean-Yves Potvin. 2003. Handbook of Metaheuristics. Springer, International Series in Operations Research & Management Science."},{"key":"e_1_3_2_12_2","volume-title":"GNU MP: The GNU Multiple Precision Arithmetic Library (6.2.0 ed.)","author":"Granlund Torbj\u00f6rn","year":"2020","unstructured":"Torbj\u00f6rn Granlund and the GMP development team. 2020. GNU MP: The GNU Multiple Precision Arithmetic Library (6.2.0 ed.). http:\/\/gmplib.org\/."},{"key":"e_1_3_2_13_2","volume-title":"CGAL User and Reference Manual (5.0.2 ed.)","author":"Hert Susan","year":"2020","unstructured":"Susan Hert and Stefan Schirra. 2020. 2D convex hulls and extreme points. In CGAL User and Reference Manual (5.0.2 ed.). CGAL Editorial Board. https:\/\/doc.cgal.org\/5.0.2\/Manual\/packages.html#PkgConvexHull2."},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.220.4598.671"},{"key":"e_1_3_2_15_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. The ACM J. of Experimental Alg. (2021). to appear.","journal-title":"The ACM J. of Experimental Alg."},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1063\/1.1699114"},{"key":"e_1_3_2_17_2","unstructured":"The ACM J. of Experimental Alg. 2021 G\u00fcnther Eder Martin Held Steinp\u00f3r Jasonarson Philipp Mayer and Peter Palfrader"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804120"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2013.01.002"},{"key":"e_1_3_2_20_2","volume-title":"CGAL User and Reference Manual (5.0.2 ed.)","author":"Tangelder Hans","year":"2019","unstructured":"Hans Tangelder and Andreas Fabri. 2019. dD spatial searching. In CGAL User and Reference Manual (5.0.2 ed.). CGAL Editorial Board. https:\/\/doc.cgal.org\/latest\/Manual\/packages.html#PkgSpatialSearchingD."},{"volume-title":"CGAL User and Reference Manual (5.0.2 ed.)","year":"2020","key":"e_1_3_2_21_2","unstructured":"The CGAL Project. 2020. CGAL User and Reference Manual (5.0.2 ed.). CGAL Editorial Board. https:\/\/doc.cgal.org\/latest\/Manual\/index.html."}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3500911","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3500911","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\/3500911"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,4]]},"references-count":20,"alternative-id":["10.1145\/3500911"],"URL":"https:\/\/doi.org\/10.1145\/3500911","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2022,3,4]]}}}