Multi-covering point set with disks

版本 1.0.1 (6.3 KB) 作者: Aaron T. Becker's Robot Swarm Lab

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.

关注

0.0

(0)

4.0 次下载

更新时间 2024/7/25

查看许可证

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, <mguitoun@CougarNet.UH.EDU>

July 25, 2024.

引用格式

Aaron T. Becker's Robot Swarm Lab (2024). Multi-covering point set with disks (https://www.mathworks.com/matlabcentral/fileexchange/169861-multi-covering-point-set-with-disks), MATLAB Central File Exchange. 检索来源 2024/8/26.