Optimal Cover of Points by Disks in a Simple Polygon
Haim Y. Kaplan, Matthew J. Katz, Gila Morgenstern, Micha Sharir · SIAM Journal on Computing · 2011
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–458]. 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.