Covering moving points with anchored disks

Consider a set of mobile clients represented by n points in the plane moving at constant speed along n different straight lines. We study the problem of covering all mobile clients using a set of k disks centered at k fixed centers. Each disk exists only at one instant and while it does, covers any client within its coverage radius. The task is to select an activation time and a radius for each disk such that every mobile client is covered by at least one disk. In particular, we study the optimization problem of minimizing the maximum coverage radius. First we prove that, although the static version of the problem is polynomial, the kinetic version is NP-hard. Moreover, we show that the problem is not approximable by a constant factor (unless P = NP). We then present a generic framework to solve it for fixed values of k, which in turn allows us to solve more general optimization problems. Our algorithms are efficient for constant values of k.

► We introduce a constrained kinetic covering problem. ► The centers are fixed in advance and the points to cover are moving on straight lines. ► We proved that the minmax version is NP-hard. ► A general framework was developed to solve a collection of optimization problems.