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. 检索时间: .

MATLAB 版本兼容性
创建方式 R2024a
兼容任何版本
平台兼容性
Windows macOS Linux
标签 添加标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

版本 已发布 发行说明
1.0.1

Fixed an error that caused an infinite loop. Now at least one radii grows each iteration.
1.0.0