{"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":1764403139782,"version":"3.41.0"},"reference-count":35,"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:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"DFG project \u201cComputational Geometry: Solving Hard Optimization Problems\u201d","award":["FE 407\/21-1"],"award-info":[{"award-number":["FE 407\/21-1"]}]},{"name":"National Science Foundation","award":["CCF-2007275, CCF-1526406"],"award-info":[{"award-number":["CCF-2007275, CCF-1526406"]}]},{"name":"US-Israel Binational Science Foundation","award":["2016116"],"award-info":[{"award-number":["2016116"]}]},{"DOI":"10.13039\/100006234","name":"Sandia National Labs","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100006234","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000185","name":"DARPA","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"<jats:p>We give an overview of theoretical and practical aspects of finding a simple polygon of minimum (<jats:sc>Min-Area<\/jats:sc>) or maximum (<jats:sc>Max-Area<\/jats:sc>) possible area for a given set of<jats:italic>n<\/jats:italic>points in the plane. Both problems are known to be<jats:italic>NP<\/jats:italic>-hard and were the subject of the 2019 Computational Geometry Challenge, which presented the quest of finding good solutions to more than 200 instances, ranging from<jats:italic>n<\/jats:italic>= 10 all the way to<jats:italic>n<\/jats:italic>= 1, 000, 000.<\/jats:p>","DOI":"10.1145\/3504000","type":"journal-article","created":{"date-parts":[[2022,3,4]],"date-time":"2022-03-04T10:43:30Z","timestamp":1646390610000},"page":"1-12","source":"Crossref","is-referenced-by-count":3,"title":["Area-Optimal Simple Polygonalizations: The CG Challenge 2019"],"prefix":"10.1145","volume":"27","author":[{"given":"Erik D.","family":"Demaine","sequence":"first","affiliation":[{"name":"CSAIL, MIT, Cambridge, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9062-4241","authenticated-orcid":false,"given":"S\u00e1ndor P.","family":"Fekete","sequence":"additional","affiliation":[{"name":"Department of Computer Science, TU Braunschweig, Braunschweig, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Phillip","family":"Keldenich","sequence":"additional","affiliation":[{"name":"Department of Computer Science, TU Braunschweig, Braunschweig, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dominik","family":"Krupke","sequence":"additional","affiliation":[{"name":"Department of Computer Science, TU Braunschweig, Braunschweig, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joseph S. B.","family":"Mitchell","sequence":"additional","affiliation":[{"name":"Department of Applied Mathematics and Statistics, Stony Brook University, Stony Brook, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,3,4]]},"reference":[{"key":"e_1_3_1_2_2","first-page":"143","volume-title":"Computer Graphics Forum","author":"Abellanas Manuel","year":"1993","unstructured":"Manuel Abellanas, Jes\u00fas Garc\u00eda, Gregorio Hern\u00e1ndez Pe\u00f1alver, Ferran Hurtado, Oriol Serra, and Jorge Urrutia. 1993. Updating polygonizations. In Computer Graphics Forum, Vol. 12. Wiley Online Library, 143\u2013152. Issue 3."},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2008.05.004"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021231927255"},{"key":"e_1_3_1_5_2","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/978-3-642-55566-4_6","volume-title":"Discrete and Computational Geometry","author":"Arkin Esther M.","year":"2003","unstructured":"Esther M. Arkin, Joseph S. B. Mitchell, S\u00e1ndor P. Fekete, Ferran Hurtado, Marc Noy, Vera Sacrist\u00e1n, and Saurabh Sethia. 2003. On the reflexivity of point sets. In Discrete and Computational Geometry. Springer, 139\u2013156."},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.5555\/648249.751880"},{"key":"e_1_3_1_7_2","volume-title":"Introduction to Geometry","author":"Coxeter Harold Scott Macdonald","year":"1969","unstructured":"Harold Scott Macdonald Coxeter. 1969. Introduction to Geometry. Wiley, New York."},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3503999"},{"key":"e_1_3_1_9_2","unstructured":"Erik D. Demaine Joseph S. B. Mitchell and Joseph O\u2019Rourke. 2001. The Open Problems Project. 573\u2013582 pages. http:\/\/cs.smith.edu\/orourke\/TOPP\/."},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3500913"},{"key":"e_1_3_1_11_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, Canada."},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009492"},{"key":"e_1_3_1_13_2","first-page":"340","article-title":"Computing nonsimple polygons of minimum perimeter","volume":"8","author":"Fekete S\u00e1ndor P.","year":"2017","unstructured":"S\u00e1ndor P. Fekete, Andreas Haas, Michael Hemmer, Michael Hoffmann, Irina Kostitsyna, Dominik Krupke, Florian Maurer, Joseph S. B. Mitchell, Arne Schmidt, Christiane Schmidt, and Julian Troegel. 2017. Computing nonsimple polygons of minimum perimeter. Journal of Computational Geometry 8, 1 (2017), 340\u2013365.","journal-title":"Journal of Computational Geometry"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3503607"},{"key":"e_1_3_1_15_2","first-page":"173","volume-title":"Symposium on Computational Geometry (SoCG)","author":"Fekete S\u00e1ndor P.","year":"1993","unstructured":"S\u00e1ndor P. Fekete and William R. Pulleyblank. 1993. Area optimization of simple polygons. In Symposium on Computational Geometry (SoCG). ACM, 173\u2013182."},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1974.11993639"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(00)00010-9"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1080\/0025570X.1976.11976535"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3500911"},{"key":"e_1_3_1_20_2","doi-asserted-by":"crossref","DOI":"10.1145\/3503953","article-title":"Optimal area polygonization by triangulation and visibility search","author":"Lepagnot Julien","year":"2022","unstructured":"Julien Lepagnot, Laurent Moalic, and Dominique Schmitt. 2022. Optimal area polygonization by triangulation and visibility search. Journal of Experimental Algorithmics (2022). This issue.","journal-title":"Journal of Experimental Algorithmics"},{"key":"e_1_3_1_21_2","volume-title":"Approximation Algorithms for Geometric Separation Problems","author":"Mitchell Joseph S. B.","year":"1993","unstructured":"Joseph S. B. Mitchell. 1993. Approximation Algorithms for Geometric Separation Problems. Technical Report. SUNY Stony Brook."},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00006-U"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1967.12000095"},{"key":"e_1_3_1_24_2","volume-title":"Polyhedral Object Models from 3D Points","author":"O\u2019Rourke Joseph","year":"1980","unstructured":"Joseph O\u2019Rourke. 1980. Polyhedral Object Models from 3D Points. Technical Report IFI-HH-M-77\/80. Universit\u00e4t Hamburg."},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.5555\/521378"},{"key":"e_1_3_1_26_2","first-page":"787","volume-title":"Handbook of Discrete and Computational Geometry","author":"O\u2019Rourke Joseph","year":"2017","unstructured":"Joseph O\u2019Rourke, Subhash Suri, and Csaba D. T\u00f3th. 2017. Polygons. In Handbook of Discrete and Computational Geometry, Csaba D. Toth, Joseph O\u2019Rourke, and Jacob E. Goodman (Eds.). CRC Press, Chapter 30, 787\u2013810."},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1115\/1.4029559"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/2896849"},{"key":"e_1_3_1_29_2","first-page":"311","article-title":"Geometrisches zur Zahlenlehre","volume":"19","author":"Pick Georg","year":"1899","unstructured":"Georg Pick. 1899. Geometrisches zur Zahlenlehre. Sitzungsberichte des Deutschen Naturwissenschaftlich-Medicinischen Vereines f\u00fcr B\u00f6hmen \u201cLotos\u201d in Prag 19 (1899), 311\u2013319.","journal-title":"Sitzungsberichte des Deutschen Naturwissenschaftlich-Medicinischen Vereines f\u00fcr B\u00f6hmen \u201cLotos\u201d in Prag"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3504001"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-7.1.378"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.3.4.376"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(87)90063-X"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2013.01.002"},{"key":"e_1_3_1_35_2","first-page":"31","volume-title":"XVII Congreso Argentino de Ciencias de la Computacion","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 XVII Congreso Argentino de Ciencias de la Computacion. 31\u201340."},{"key":"e_1_3_1_36_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\/3504000","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3504000","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3504000","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\/3504000"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,4]]},"references-count":35,"alternative-id":["10.1145\/3504000"],"URL":"https:\/\/doi.org\/10.1145\/3504000","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]]}}}