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

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

## Claudio Contardo et Alain Hertz

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