{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:26:34Z","timestamp":1787340394857,"version":"build-2736575974"},"reference-count":31,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2011,1]]},"abstract":"<jats:p>Let P be a simple polygon, and let Q be a set of points in P. We present an almost-linear time algorithm for computing a minimum cover of Q by disks that are contained in P. We then generalize the algorithm so that it can compute a minimum cover of Q by homothets of any fixed compact convex set ${\\cal O}$ of constant description complexity that are contained in P. This improves previous results of Katz and Morgenstern [Lecture Notes in Comput. Sci. 5664, 2009, pp. 447\u2013458]. We also consider the minimum disk-cover problem when Q is contained in a (sufficiently narrow) annulus and present a nearly linear algorithm for this case, too.<\/jats:p>","DOI":"10.1137\/100808459","type":"journal-article","created":{"date-parts":[[2011,12,15]],"date-time":"2011-12-15T19:09:30Z","timestamp":1323976170000},"page":"1647-1661","source":"Crossref","is-referenced-by-count":3,"title":["Optimal Cover of Points by Disks in a Simple Polygon"],"prefix":"10.1137","volume":"40","author":[{"given":"Haim","family":"Kaplan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Matthew J.","family":"Katz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gila","family":"Morgenstern","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Micha","family":"Sharir","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2011,12,15]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/0216006"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"J. Boissonnat and M. Yvinec,\n                      Algorithmic Geometry\n                      , Cambridge University Press, Cambridge, UK, 1998.","DOI":"10.1017\/CBO9781139172998"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1007\/BF02570718"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(80)90015-2"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(74)90002-8"},{"key":"R6","first-page":"101","volume":"9","author":"Calinescu G.","year":"2004","journal-title":"MONET"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"P. Carmi, M. J. Katz, and N. Lev-Tov,\n                      Covering points by unit disks of fixed location\n                      , in Proceedings of the 18th International Symposium on Algorithms and Computation, 2007, pp. 644\u2013655.","DOI":"10.1007\/978-3-540-77120-3_56"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"L. P. Chew and R. L. Drysdale III,\n                      Voronoi diagrams based on convex distance functions\n                      , in Proceedings of the 1st Annual Symposium on Computational Geometry, (1985), pp. 235\u2013244.","DOI":"10.1145\/323233.323264"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009429"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1137\/0201013"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(74)90094-X"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"M. C. Golumbic,\n                      Algorithmic Graph Theory and Perfect Graphs\n                      , Academic Press, New York, 1980.","DOI":"10.1016\/B978-0-12-289260-8.50010-8"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz, and A. Schrijver,\n                      Polynomial algorithms for perfect graphs\n                      , in Topics on Perfect Graphs, C. Berge and V. Chv\u00e1tal, eds., Ann. Discrete Math. 21, North-Holland, Amsterdam, 1984, pp. 325\u2013356.","DOI":"10.1016\/S0304-0208(08)72943-8"},{"key":"R14","unstructured":"D. Halperin and C. Linhart,\n                      The minimum enclosing disk with obstacles\n                      , 1999, unpublished manuscript."},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1194"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1145\/2455.214106"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90165-E"},{"key":"R18","unstructured":"F. Hurtado, V. Sacrist\u00e1n, and G. Toussaint,\n                      Some constrained minimax and maximin location problems\n                      , Stud. Locat. Anal. 15, 2000, pp. 17\u201335."},{"key":"R19","doi-asserted-by":"crossref","unstructured":"M. J. Katz and G. Morgenstern,\n                      A scheme for computing minimum covers within simple regions\n                      , in Proceedings of the 11th International Symposium on Algorithms and Data Structures (WADS), Lecture Notes in Comput. Sci. 5664, Springer Verlag, 2009, pp. 447\u2013458.","DOI":"10.1007\/978-3-642-03367-4_39"},{"key":"R20","unstructured":"M. J. Katz and G. Morgenstern,\n                      Guarding orthogonal art galleries with sliding cameras\n                      , in Proceedings of the 25th European Workshop on Computational Geometry, 2009, pp. 159\u2013162."},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2007.02.002"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187683"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1137\/0212002"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187867"},{"key":"R25","unstructured":"N. Miller and M. Sharir,\n                      Efficient Randomized Algorithms for Constructing the Union of Fat Triangles and of Pseudo-Disks\n                      , M.Sc. thesis, Tel-Aviv University, Tel-Aviv, Israel, 1991."},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1137\/0402033"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(90)90017-F"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"N. H. Mustafa and S. Ray,\n                      PTAS for geometric hitting set problems via local search\n                      , in Proceedings of the 25th Annual Symposium on Computational Geometry, (2009), pp. 17\u201322.","DOI":"10.1145\/1542362.1542367"},{"key":"R29","unstructured":"S. Narayanappa and P. Vojtechovsk\u00fd,\n                      An improved approximation factor for the unit disk covering problem\n                      , in Proceedings of the 18th Canadian Conference on Computational Geometry, 2006, pp. 15\u201318."},{"key":"R30","unstructured":"M. Sharir and P. K. Agarwal,\n                      Davenport-Schinzel Sequences and their Geometric Applications\n                      , Cambridge University Press, New York, 1995."},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195907002264"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/100808459","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:33:04Z","timestamp":1787337184000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/100808459"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1]]},"references-count":31,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["10.1137\/100808459"],"URL":"https:\/\/doi.org\/10.1137\/100808459","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1]]}}}