Groupe d’études et de recherche en analyse des décisions


An exact algorithm for a class of geometric set-cover problems


Given a set \(\mathcal{R}\) of m disjoint finite regions in the 2-dimensional plane, all regions having polygonal boundaries, and given a set \(\mathcal{D}\) of n discs with fixed centers and radii, we consider the problem of finding a minimum cardinality subset \(\mathcal{D}^*\subseteq \mathcal{D}\) such that every point in \(\mathcal{R}\) is covered by at least one disc in \(\mathcal{D}^*\). We show that this problem can be solved by using an iterative procedure that alternates between the solution of a traditional set-cover problem and the construction of the Laguerre-Voronoi diagram of a circle set.

, 15 pages