\input zb-basic
\input zb-ioport
\iteman{io-port 05779799}
\itemau{Kaplan, Haim; Katz, Matthew J.; Morgenstern, Gila; Sharir, Micha}
\itemti{Optimal cover of points by disks in a simple polygon.}
\itemso{de Berg, Mark (ed.) et al., Algorithms -- ESA 2010. 18th annual European symposium, Liverpool, UK, September 6--8, 2010. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-15774-5/pbk). Lecture Notes in Computer Science 6346, 475-486 (2010).}
\itemab
Summary: 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 any fixed compact convex set $\mathcal{O}$ of constant description complexity that are contained in $P$. This improves previous results of Katz and Morgenstern [20]. We also consider the disk-cover problem when $Q$ is contained in a (not too wide) annulus, and present a nearly linear algorithm for this case too.
\itemrv{~}
\itemcc{}
\itemut{}
\itemli{doi:10.1007/978-3-642-15775-2\_41}
\end