{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T11:21:24Z","timestamp":1770895284429,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":51,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T00:00:00Z","timestamp":1717977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"VILLUM Foundation grant","award":["16582"],"award-info":[{"award-number":["16582"]}]},{"name":"Independent Research Fund Denmark under the Sapere Aude research career programme","award":["Starting Grant 1054-00032B"],"award-info":[{"award-number":["Starting Grant 1054-00032B"]}]},{"name":"Google Ph.D. Fellowship","award":[""],"award-info":[{"award-number":[""]}]},{"name":"Swedish Research Council","award":["Reg.~No.~2019-05622"],"award-info":[{"award-number":["Reg.~No.~2019-05622"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,6,10]]},"DOI":"10.1145\/3618260.3649756","type":"proceedings-article","created":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T19:25:02Z","timestamp":1718133902000},"page":"904-910","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Minimum Star Partitions of Simple Polygons in Polynomial Time"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2734-4690","authenticated-orcid":false,"given":"Mikkel","family":"Abrahamsen","sequence":"first","affiliation":[{"name":"University of Copenhagen, Copenhagen, Denmark"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-0874-2356","authenticated-orcid":false,"given":"Joakim","family":"Blikstad","sequence":"additional","affiliation":[{"name":"KTH Royal Institute of Technology, Stockholm, Sweden \/ MPI-INF, Saarbr\u00fccken, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6349-869X","authenticated-orcid":false,"given":"Andr\u00e9","family":"Nusser","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Copenhagen, Denmark"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3149-7799","authenticated-orcid":false,"given":"Hanwen","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Copenhagen, Denmark"}]}],"member":"320","published-online":{"date-parts":[[2024,6,11]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3486220"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/5383.5387"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90005-2"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(81)90002-9"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221025"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cie"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1115\/1.1596579"},{"key":"e_1_3_2_1_10_1","volume-title":"33rd Canadian Conference on Computational Geometry (CCCG 2021 ). 175-184","author":"Buchin Maike","year":"2021","unstructured":"Maike Buchin and Leonie Selbach. 2021. Decomposing Polygons into Fat Components. In 33rd Canadian Conference on Computational Geometry (CCCG 2021 ). 175-184."},{"key":"e_1_3_2_1_11_1","volume-title":"Computational geometry and convexity. Ph. D. Dissertation","author":"Chazelle Bernard","unstructured":"Bernard Chazelle. 1980. Computational geometry and convexity. Ph. D. Dissertation. Yale University."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1982.58"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213031"},{"key":"e_1_3_2_1_14_1","first-page":"145","article-title":"Approximation and decomposition of shapes. In Algorithmic and Geometric Aspects of Robotics, Jacob T. Schwartz and Chee-Keng Yap (Eds.)","volume":"1","author":"Chazelle Bernard","year":"1987","unstructured":"Bernard Chazelle. 1987. Approximation and decomposition of shapes. In Algorithmic and Geometric Aspects of Robotics, Jacob T. Schwartz and Chee-Keng Yap (Eds.). Advances in Robotics, Vol. 1. 145-185.","journal-title":"Advances in Robotics"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","unstructured":"Bernard Chazelle. 1991. Triangulating a Simple Polygon in Linear Time. Discret. Comput. Geom. 6 ( 1991 ) 485-524. https:\/\/doi.org\/10.1007\/BF02574703 10.1007\/BF02574703","DOI":"10.1007\/BF02574703"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-444-87806-9"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","unstructured":"Bernard Chazelle and Leonidas Palios. 1994. Decomposition algorithms in geometry. In Algebraic Geometry and its applications Chandrajit L. Bajaj (Ed.). 419-447. https:\/\/doi.org\/10.1007\/978-1-4612-2628-4_27 10.1007\/978-1-4612-2628-4_27","DOI":"10.1007\/978-1-4612-2628-4_27"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","unstructured":"Bernard Chazelle and Leonidas Palios. 1997. Decomposing the Boundary of a Nonconvex Polyhedron. Algorithmica 17 3 ( 1997 ) 245-265. https:\/\/doi.org\/10. 1007\/BF02523191 10.1007\/BF02523191","DOI":"10.1007\/BF02523191"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(75)90061-1"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1092-3"},{"key":"e_1_3_2_1_22_1","volume-title":"Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG 2003 ). 43-46","author":"Damian-Iordache Mirela","year":"2003","unstructured":"Mirela Damian-Iordache and Joseph O'Rourke. 2003. Partitioning Regular Polygons into Circular Pieces I: Convex Partitions. In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG 2003 ). 43-46. http:\/\/www.cccg.ca\/proceedings\/2003\/27.pdf"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36279-8_17"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/2945.582388"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/T-C"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","unstructured":"Steve Fisk. 1978. A short proof of Chv\u00e1tal's Watchman Theorem. J. Comb. Theory Ser. B 24 3 ( 1978 ) 374. https:\/\/doi.org\/10.1016\/ 0095-8956 ( 78 ) 90059-X 10.1016\/0095-8956(78)90059-X","DOI":"10.1016\/0095-8956(78)90059-X"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90062-5"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214056"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-044482537-7"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-444-87806-9"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195902000803"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.2312\/SPBG"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/IROS"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90097-X"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01759071"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/323233.323247"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/262839"},{"key":"e_1_3_2_1_39_1","volume-title":"Art Gallery Theorems and Algorithms","author":"O'Rourke Joseph","unstructured":"Joseph O'Rourke. 1987. Art Gallery Theorems and Algorithms. Oxford University Press."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1201\/9781315119601"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1504\/IJCAET"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/38.365005"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.163407"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-009-7772-3_7"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","unstructured":"Marc J. van Kreveld. 1998. On fat partitioning fat covering and the union size of polygons. Comput. Geom. 9 4 ( 1998 ) 197-210. https:\/\/doi.org\/10.1016\/S0925-7721 ( 96 ) 00016-8 10.1016\/S0925-7721(96)00016-8","DOI":"10.1016\/S0925-7721"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.15607\/RSS"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","unstructured":"Jiazhi Xia Ying He Shuchu Han Chi-Wing Fu Feng Luo and Xianfeng Gu. 2010. Parameterization of star-shaped volumes using Green's functions. In Advances in Geometric Modeling and Processing (GMP 2010 ). 219-235. https: \/\/doi.org\/10.1007\/978-3-642-13411-1_15 10.1007\/978-3-642-13411-1_15","DOI":"10.1007\/978-3-642-13411-1_15"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT"}],"event":{"name":"STOC '24: 56th Annual ACM Symposium on Theory of Computing","location":"Vancouver BC Canada","acronym":"STOC '24","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 56th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649756","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3618260.3649756","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:52Z","timestamp":1750291432000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649756"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,10]]},"references-count":51,"alternative-id":["10.1145\/3618260.3649756","10.1145\/3618260"],"URL":"https:\/\/doi.org\/10.1145\/3618260.3649756","relation":{},"subject":[],"published":{"date-parts":[[2024,6,10]]},"assertion":[{"value":"2024-06-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}