{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:57:42Z","timestamp":1781078262813,"version":"3.54.1"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T00:00:00Z","timestamp":1648598400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council under the European Union\u2019s Seventh Framework Programme","award":["FP\/2007-2013"],"award-info":[{"award-number":["FP\/2007-2013"]}]},{"name":"ERC","award":["280152, 725978, and 267959"],"award-info":[{"award-number":["280152, 725978, and 267959"]}]},{"DOI":"10.13039\/501100004281","name":"Polish National Science Centre","doi-asserted-by":"crossref","award":["DEC-2013\/11\/D\/ST6\/03073"],"award-info":[{"award-number":["DEC-2013\/11\/D\/ST6\/03073"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2022,4,30]]},"abstract":"\n We study a general family of facility location problems defined on planar graphs and on the two-dimensional plane. In these problems, a subset of\n k<\/jats:italic>\n objects has to be selected, satisfying certain packing (disjointness) and covering constraints. Our main result is showing that, for each of these problems, the\n \n n\n O<\/jats:sup>\n <\/jats:italic>\n (\u221a\n k<\/jats:italic>\n ) time brute force algorithm of selecting\n k<\/jats:italic>\n objects can be improved to\n \n n\n O<\/jats:sup>\n <\/jats:italic>\n (\u221a\n k<\/jats:italic>\n ) time. The algorithm is based on an idea that was introduced recently in the design of geometric QPTASs, but was not yet used for exact algorithms and for planar graphs. We focus on the Voronoi diagram of a hypothetical solution of\n k<\/jats:italic>\n objects, guess a balanced separator cycle of this Voronoi diagram to obtain a set that separates the solution in a balanced way, and then recurse on the resulting subproblems.\n <\/jats:p>\n \n The following list is an exemplary selection of concrete consequences of our main result. We can solve each of the following problems in time\n \n n\n O<\/jats:sup>\n <\/jats:italic>\n (\u221a\n k<\/jats:italic>\n ), where\n n<\/jats:italic>\n is the total size of the input:\n \n \n \n \n d<\/jats:italic>\n -Scattered Set\n <\/jats:sc>\n : find\n k<\/jats:italic>\n vertices in an edge-weighted planar graph that pairwise are at distance at least\n d<\/jats:italic>\n from each other (\n d<\/jats:italic>\n is part of the input).\n <\/jats:p>\n <\/jats:list-item>\n \n \n \n d<\/jats:italic>\n -Dominating Set\n <\/jats:sc>\n (or (\n k,d<\/jats:italic>\n )-Center): find\n k<\/jats:italic>\n vertices in an edge-weighted planar graph such that every vertex of the graph is at distance at most\n d<\/jats:italic>\n from at least one selected vertex (\n d<\/jats:italic>\n is part of the input).\n <\/jats:p>\n <\/jats:list-item>\n \n \n Given a set\n D<\/jats:italic>\n of connected vertex sets in a planar graph\n G<\/jats:italic>\n , find\n k<\/jats:italic>\n disjoint vertex sets in\n D<\/jats:italic>\n .\n <\/jats:p>\n <\/jats:list-item>\n \n \n Given a set\n D<\/jats:italic>\n of disks in the plane (of possibly different radii), find\n k<\/jats:italic>\n disjoint disks in\n D<\/jats:italic>\n .\n <\/jats:p>\n <\/jats:list-item>\n \n \n Given a set\n D<\/jats:italic>\n of simple polygons in the plane, find\n k<\/jats:italic>\n disjoint polygons in\n D<\/jats:italic>\n .\n <\/jats:p>\n <\/jats:list-item>\n \n \n Given a set\n D<\/jats:italic>\n of disks in the plane (of possibly different radii) and a set\n P<\/jats:italic>\n of points, find\n k<\/jats:italic>\n disks in\n D<\/jats:italic>\n that together cover the maximum number of points in\n P<\/jats:italic>\n .\n <\/jats:p>\n <\/jats:list-item>\n \n \n Given a set\n D<\/jats:italic>\n of axis-parallel squares in the plane (of possibly different sizes) and a set\n P<\/jats:italic>\n of points, find\n k<\/jats:italic>\n squares in\n D<\/jats:italic>\n that together cover the maximum number of points in\n P<\/jats:italic>\n .\n <\/jats:p>\n <\/jats:list-item>\n <\/jats:list>\n <\/jats:p>\n \n It is known from previous work that, assuming the Exponential Time Hypothesis (ETH), there is no\n f<\/jats:italic>\n (\n k<\/jats:italic>\n )\n \n n\n o<\/jats:sup>\n <\/jats:italic>\n (\u221a\n k<\/jats:italic>\n ) time algorithm for any computable function\n f<\/jats:italic>\n for any of these problems. Furthermore, we give evidence that packing problems have\n \n n\n O<\/jats:sup>\n <\/jats:italic>\n (\u221a\n k<\/jats:italic>\n ) time algorithms for a much more general class of objects than covering problems have. For example, we show that, assuming ETH, the problem where a set\n D<\/jats:italic>\n of axis-parallel rectangles and a set\n P<\/jats:italic>\n of points are given, and the task is to select\n k<\/jats:italic>\n rectangles that together cover the entire point set, does not admit an\n f<\/jats:italic>\n (\n k<\/jats:italic>\n )\n \n n\n o<\/jats:sup>\n <\/jats:italic>\n (\n k<\/jats:italic>\n ) time algorithm for any computable function\n f<\/jats:italic>\n .\n <\/jats:p>","DOI":"10.1145\/3483425","type":"journal-article","created":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T09:25:07Z","timestamp":1648632307000},"page":"1-64","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams"],"prefix":"10.1145","volume":"18","author":[{"given":"D\u00e1niel","family":"Marx","sequence":"first","affiliation":[{"name":"CISPA Helmholtz Center for Information Security, Saarbr\u00fccken, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Warsaw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,3,30]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3326122"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.50"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.49"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446591"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0110-y"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.10.001"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2019.26"},{"issue":"2","key":"e_1_3_2_9_2","article-title":"Optimization problems in multiple-interval graphs","volume":"6","author":"Butman Ayelet","year":"2010","unstructured":"Ayelet Butman, Danny Hermelin, Moshe Lewenstein, and Dror Rawitz. 2010. Optimization problems in multiple-interval graphs. ACM Trans. Algor. 6, 2 (2010).","journal-title":"ACM Trans. Algor."},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2012.04.001"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.04.007"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.129"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2019.33"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00050"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.6"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480103433410"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/1077464.1077468"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/1101821.1101823"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm033"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-008-2140-4"},{"key":"e_1_3_2_22_2","first-page":"517","volume-title":"Proceedings of the International Symposium on Graph Drawing","author":"Demaine Erik D.","year":"2004","unstructured":"Erik D. Demaine and Mohammad Taghi Hajiaghayi. 2004. Fast algorithms for hard graph problems: Bidimensionality, minors, and local treewidth. In Proceedings of the International Symposium on Graph Drawing. 517\u2013533."},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2013.11.006"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2008.02.004"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9296-1"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SWAT.2018.19"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.09.065"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29344-3_30"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.05.016"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24749-4_6"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702419649"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9828-6"},{"key":"e_1_3_2_33_2","unstructured":"Sariel Har-Peled. 2009. Being fat and friendly is not enough. Retrieved from http:\/\/arxiv.org\/abs\/0908.2369."},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/2582112.2582157"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/2455.214106"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01185335"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9651-5"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.01.025"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_48"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.131"},{"key":"e_1_3_2_42_2","first-page":"41","article-title":"Lower bounds based on the Exponential Time Hypothesis","volume":"105","author":"Lokshtanov Daniel","year":"2011","unstructured":"Daniel Lokshtanov, D\u00e1niel Marx, and Saket Saurabh. 2011. Lower bounds based on the Exponential Time Hypothesis. Bull. EATCS 105 (2011), 41\u201372.","journal-title":"Bull. EATCS"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_41"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/11847250_14"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.26"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2010.v006a005"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_57"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_72"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00052"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/2582112.2582124"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1137\/14099317X"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/3239560"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00670-w"},{"key":"e_1_3_2_54_2","first-page":"1065","volume-title":"Proceedings of the SODA 2010","author":"P\u0103tra\u015fcu Mihai","year":"2010","unstructured":"Mihai P\u0103tra\u015fcu and Ryan Williams. 2010. On the possibility of faster SAT algorithms. In Proceedings of the SODA 2010. 1065\u20131075."},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215352"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1998.743449"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-23719-5_31"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3483425","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3483425","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:58Z","timestamp":1750191538000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3483425"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,30]]},"references-count":56,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,4,30]]}},"alternative-id":["10.1145\/3483425"],"URL":"https:\/\/doi.org\/10.1145\/3483425","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,30]]},"assertion":[{"value":"2019-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-03-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}