Retour

G-2020-17

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

et

référence BibTeX

Given a set R of m disjoint finite regions in the 2-dimensional plane, all regions having polygonal boundaries, and given a set D of n discs with fixed centers and radii, we consider the problem of finding a minimum cardinality subset DD such that every point in R is covered by at least one disc in 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

Axe de recherche

Application de recherche

Publication