Multi-covering point set with disks

Given a 2D point set X where each point must be covered k times, determines radii for discs centered at points Y that meet the requirement.

Determines disc radiis for sensors placed at Y to cover points at X the required number of times (k). This is a 'multi-covering with disks' problem.

This code implements Algorithm 1 described in the paper:

Bhowmick, S., Varadarajan, K., & Xue, S.-K. (2013). "A constant-factor approximation for multi-covering with disks." In Proceedings of the twenty-ninth annual symposium on Computational geometry (pp. 243-248). https://doi.org/10.48550/arXiv.1407.5674

Abstract: "We consider variants of the following multi-covering problem with disks. We are given two point sets Y (servers) and X (clients) in the plane, a coverage function κ:X→, and a constant α≥1. Centered at each server is a single disk whose radius we are free to set. The requirement is that each client x∈X be covered by at least κ(x) of the server disks. The objective function we wish to minimize is the sum of the α-th powers of the disk radii. We present a polynomial time algorithm for this problem achieving an O(1) approximation."

Credit goes to the original authors for their work on developing this algorithm.

Implemented in Matlab by Mariem Guitouni, <[e-mail]>

July 25, 2024.