Optimal Cover of Points by Disks in a Simple Polygon

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 generalize the algorithm above, so that it can compute a minimum cover of Q by homothets of a xed compact convex set of constant description complexity O that are contained in P. This improves previous results of Katz and Morgen- stern (19). We also consider the disk-cover problem when Q is contained in a (not too wide) annulus, and present an O(jQjlogjQj) algorithm for this case. Let P be a simple n-gon in the plane, and let Q be a set of m points in P. A disk cover of Q with respect to P is a set D of disks (of variable radii), such that the union of the disks of D covers (i.e., contains) Q and is contained in P. In other words, each disk D ∈ D is contained in P , and each point q ∈ Q, lies in at least one disk D ∈ D. A minimum disk cover of Q with respect to P is a disk cover of Q with respect to P of minimum cardinality. The problem of computing a minimum disk cover of Q with respect to P was introduced and studied by Katz and Morgenstern (19). They also considered the case where the covering objects are homothets (contained in P ) of a fixed compact convex set O of constant description complexity. In both cases, exact polynomial-time solutions were presented. In this paper we present alternative and significantly faster solutions for both disks and homothets, and also consider a third new case, as mentioned in the abstract and detailed below. All our solutions run in close to linear time.