G-2020-17
An exact algorithm for a class of geometric set-cover problems
and BibTeX reference
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
Research Axis
Research application
Publication
Sep 2021
and
Discrete Applied Mathematics, 300, 25–35, 2021
BibTeX reference