### G-2020-17

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

## Claudio Contardo and 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.

Published **February 2020**
,
15 pages