{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:46:36Z","timestamp":1750308396477,"version":"3.41.0"},"reference-count":5,"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"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"<jats:p>In this article, we present our heuristic solutions to the problems of finding the maximum and minimum area polygons with a given set of vertices. Our solutions are based mostly on two simple algorithmic paradigms: greedy and local search. The greedy heuristic starts with a simple polygon and adds vertices one by one, according to a weight function. A crucial ingredient to obtain good solutions is the choice of an appropriate weight function that avoids long edges, since long edges impede the insertion of too many different edges later on. The local search part consists of moving consecutive vertices to another location in the polygonal chain. We also discuss the different implementation techniques that are necessary to reduce the running time.<\/jats:p>","DOI":"10.1145\/3503999","type":"journal-article","created":{"date-parts":[[2022,3,17]],"date-time":"2022-03-17T11:10:50Z","timestamp":1647515450000},"page":"1-11","source":"Crossref","is-referenced-by-count":1,"title":["Greedy and Local Search Heuristics to Build Area-Optimal Polygons"],"prefix":"10.1145","volume":"27","author":[{"given":"Lo\u00efc","family":"Crombez","sequence":"first","affiliation":[{"name":"LIMOS, Universit\u00e9 Clermont Auvergne, Clermont-Fd, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9807-028X","authenticated-orcid":false,"given":"Guilherme D.","family":"da Fonseca","sequence":"additional","affiliation":[{"name":"LIS, Aix-Marseille Universit\u00e9, Marseille, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yan","family":"Gerard","sequence":"additional","affiliation":[{"name":"LIMOS, Universit\u00e9 Clermont Auvergne, Clermont-Fd, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,3,17]]},"reference":[{"key":"e_1_3_1_2_2","article-title":"The 2019 CG challenge: Area-Optimal polygonalizations","author":"Demaine Erik D.","year":"2022","unstructured":"Erik D. Demaine, S\u00e1ndor P. Fekete, and Joseph S. B. Mitchell. 2022. The 2019 CG challenge: Area-Optimal polygonalizations. arXiv:2111.07304. Retrieved from https:\/\/arxiv.org\/abs\/2111.07304.","journal-title":"arXiv:2111.07304"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009492"},{"key":"e_1_3_1_4_2","doi-asserted-by":"crossref","unstructured":"S\u00e1ndor P. Fekete Andreas Haas Phillip Keldenich Michael Perk and Arne Schmidt. 2022. Computing area-optimal simple polygonalizations. arXiv:2111.05386. Retrieved from https:\/\/arxiv.org\/abs\/2111.05386.","DOI":"10.1145\/3503607"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.5555\/521378"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/2896849"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3503999","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3503999","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:45:05Z","timestamp":1750268705000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3503999"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,17]]},"references-count":5,"alternative-id":["10.1145\/3503999"],"URL":"https:\/\/doi.org\/10.1145\/3503999","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]]}}}