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

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 D * subset of D 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. Computer experiments demonstrate the effectiveness of the proposed algorithm, particularly when the number vertical bar D*vertical bar of discs necessary to cover R is low. (C) 2021 Elsevier B.V. All rights reserved.

Automated summary

The paper introduces an algorithm to find the minimum number of disks needed to cover a given region by alternating between solving a set-cover problem and constructing a Laguerre-Voronoi diagram of circle set. Experimental results demonstrate the effectiveness of the proposed algorithm, especially when a small number of disks are required to cover the region.