• Calendar

June 23, Wednesday
12:00 – 13:30

Let $X$ be a simple region, and let $Q$ be a set of $m$ points in $X$. A disk cover of $Q$ with respect to $X$, is a set of disks (of variable radii), such that the union of these disks covers $Q$ and is contained in $X$. In other words: (i) each disk in the cover is contained in $X$, and (ii) each point $q in Q$, lies in a disk of the cover. A minimum disk cover of $Q$ with respect to $X$ is a disk cover of $Q$ with respect to $X$ of minimum cardinality. The problem of computing a minimum disk cover of a point set $Q$ with respect to a simple region $X$ arises, e.g., in the following setting. $X$ represents a secured area, and each point of $Q$ represents a client of a radio network. One must place the smallest possible number of transmitters, such that each client is served by at least one of the transmitters (i.e., is within the transmission range of at least one of the transmitters), and any point outside the area, is outside the range of each of the transmitters. Surprisingly, this problem is solvable in polynomial time, due to very nice combinatorial structure. In a paper presented at WADS 2009 and recently accepted to Algorithmica, we presented an exact polynomial time algorithm for the above problem (joint work with Matya Katz). In a paper accepted to ESA 2010 we give an improved almost-linear time algorithm (Joint work with Haim Kaplan, Matya Katz and Micha Sharir). I'll give the highlights of the proof, which I find simple, nice and elegant.