{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:17:24Z","timestamp":1750220244942,"version":"3.41.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2022,12,31]],"date-time":"2022-12-31T00:00:00Z","timestamp":1672444800000},"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>The aim of the \u201cCG:SHOP Challenge 2019\u201d was to generate optimal area polygonizations of a planar point set. We describe here the algorithm that won the challenge. It is a two-phase algorithm based on the node-insertion move technique, which comes from the TSP. In the first phase, we use constrained triangulations to check efficiently the simplicity of the generated polygonizations. In the second phase, we perform visibility searches to be able to generate a wider variety of polygonizations. In both phases, the simulated annealing metaheuristic is implemented to approach the optimum.<\/jats:p>","DOI":"10.1145\/3503953","type":"journal-article","created":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T13:31:26Z","timestamp":1676986286000},"page":"1-23","source":"Crossref","is-referenced-by-count":2,"title":["Optimal Area Polygonization by Triangulation and Visibility Search"],"prefix":"10.1145","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0152-6613","authenticated-orcid":false,"given":"Julien","family":"Lepagnot","sequence":"first","affiliation":[{"name":"Universit\u00e9 de Haute-Alsace, IRIMAS UR 7499, Mulhouse, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3749-3227","authenticated-orcid":false,"given":"Laurent","family":"Moalic","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Haute-Alsace, IRIMAS UR 7499,  Mulhouse, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1606-8013","authenticated-orcid":false,"given":"Dominique","family":"Schmitt","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Haute-Alsace, IRIMAS UR 7499, Mulhouse, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,2,21]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.5555\/286762"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2008.04.001"},{"key":"e_1_3_2_4_2","volume-title":"30th European Workshop on Computational Geometry","author":"Bungiu Francisc","year":"2014","unstructured":"Francisc Bungiu, Michael Hemmerand, John Hershberger, Kan Huang, and Alexander Kr\u00f6ller. 2014. Efficient computation of visibility polygons. In 30th European Workshop on Computational Geometry. Ein-Gedi, Israel."},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574703"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-11509-8_4"},{"key":"e_1_3_2_7_2","first-page":"Submitted","article-title":"Greedy and local search solutions to the minimum and maximum area polygons","author":"Crombez Lo\u00efc","year":"2020","unstructured":"Lo\u00efc Crombez, Guilherme D. da Fonseca, and Yan Gerard. 2020. Greedy and local search solutions to the minimum and maximum area polygons. Journal of Experimental Algorithmics (2020), Submitted.","journal-title":"Journal of Experimental Algorithmics"},{"key":"e_1_3_2_8_2","first-page":"Submitted","article-title":"Area-Optimal simple polygonalizations: The CG challenge 2019","author":"Demaine Erik D.","year":"2020","unstructured":"Erik D. Demaine, S\u00e1ndor P. Fekete, Phillip Keldenich, Dominik Krupke, and Joseph S. B. Mitchell. 2020. Area-Optimal simple polygonalizations: The CG challenge 2019. Journal of Experimental Algorithmics (2020), Submitted.","journal-title":"Journal of Experimental Algorithmics"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492900001331"},{"key":"e_1_3_2_10_2","first-page":"Submitted","article-title":"2-Opt moves and flips for area-optimal polygonalizations","author":"Eder G\u00fcnther","year":"2020","unstructured":"G\u00fcnther Eder, Martin Held, Steinthor Jasonarson, Philipp Mayer, and Peter Palfrader. 2020. 2-Opt moves and flips for area-optimal polygonalizations. Journal of Experimental Algorithmics (2020), Submitted.","journal-title":"Journal of Experimental Algorithmics"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2018.01.004"},{"issue":"2","key":"e_1_3_2_12_2","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1016\/0196-6774(81)90019-5","article-title":"A linear algorithm for computing the visibility polygon from a point","volume":"2","author":"Gindy Hossam El","year":"1981","unstructured":"Hossam El Gindy and David Avis. 1981. A linear algorithm for computing the visibility polygon from a point. Journal of Algorithms 2, 2 (1981), 186\u2013197.","journal-title":"Journal of Algorithms"},{"key":"e_1_3_2_13_2","first-page":"Submitted","article-title":"Computing area-optimal simple polygonalizations","author":"Fekete S\u00e1ndor P.","year":"2020","unstructured":"S\u00e1ndor P. Fekete, Andreas Haas, Phillip Keldenich, Michael Perk, and Arne Schmidt. 2020. Computing area-optimal simple polygonalizations. Journal of Experimental Algorithmics (2020), Submitted.","journal-title":"Journal of Experimental Algorithmics"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511543340"},{"key":"e_1_3_2_15_2","first-page":"Submitted","article-title":"Area-optimal polygonization using simulated annealing","author":"Goren Nir","year":"2020","unstructured":"Nir Goren, Efi Fogel, and Dan Halperin. 2020. Area-optimal polygonization using simulated annealing. Journal of Experimental Algorithmics (2020), Submitted.","journal-title":"Journal of Experimental Algorithmics"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0028-4"},{"issue":"1","key":"e_1_3_2_17_2","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1142\/S021819592050003X","article-title":"Dynamic algorithms for visibility polygons in simple polygons","volume":"30","author":"Inkulu R.","year":"2020","unstructured":"R. Inkulu, K. Sowmya, and Nitish P. Thakur. 2020. Dynamic algorithms for visibility polygons in simple polygons. International Journal of Computational Geometry & Applications 30, 1 (2020), 51\u201378.","journal-title":"International Journal of Computational Geometry & Applications"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01937271"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.220.4598.671"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/0734-189X(83)90065-8"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187695"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90086-X"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.5555\/289380"},{"key":"e_1_3_2_24_2","first-page":"Submitted","article-title":"Heuristics for area optimal polygonizations","author":"Ramos Natanael","year":"2020","unstructured":"Natanael Ramos, Rai Caetan de Jesus, Pedro de Rezende, Cid de Souza, and Fabio Luiz Usberti. 2020. Heuristics for area optimal polygonizations. Journal of Experimental Algorithmics (2020), Submitted.","journal-title":"Journal of Experimental Algorithmics"},{"key":"e_1_3_2_25_2","volume-title":"The Traveling Salesman: Computational Solutions for TSP Applications","author":"Reinelt Gerhard","year":"1994","unstructured":"Gerhard Reinelt. 1994. The Traveling Salesman: Computational Solutions for TSP Applications. Springer-Verlag, Berlin."},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(91)90012-4"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3503953","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3503953","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:32Z","timestamp":1750188632000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3503953"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,31]]},"references-count":25,"alternative-id":["10.1145\/3503953"],"URL":"https:\/\/doi.org\/10.1145\/3503953","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2022,12,31]]}}}