G-2020-17
An exact algorithm for a class of geometric set-cover problems
et référence BibTeX
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.
Paru en février 2020 , 15 pages
Axe de recherche
Application de recherche
Publication
sept. 2021
et
Discrete Applied Mathematics, 300, 25–35, 2021
référence BibTeX