Multi-Covering a Point Set by $m$ Disks with Minimum Total Area
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916620728795136 |
|---|---|
| author | Guitouni, Mariem Loi, Chek-Manh Fekete, Sándor P. Perk, Michael Becker, Aaron T. |
| author_facet | Guitouni, Mariem Loi, Chek-Manh Fekete, Sándor P. Perk, Michael Becker, Aaron T. |
| contents | A common robotics sensing problem is to place sensors to robustly monitor a set of assets, where robustness is assured by requiring asset $p$ to be monitored by at least $κ(p)$ sensors. Given $n$ assets that must be observed by $m$ sensors, each with a disk-shaped sensing region, where should the sensors be placed to minimize the total area observed? We provide and analyze a fast heuristic for this problem. We then use the heuristic to initialize an exact Integer Programming solution. Subsequently, we enforce separation constraints between the sensors by modifying the integer program formulation and by changing the disk candidate set. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_13773 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Multi-Covering a Point Set by $m$ Disks with Minimum Total Area Guitouni, Mariem Loi, Chek-Manh Fekete, Sándor P. Perk, Michael Becker, Aaron T. Robotics Computational Geometry F.2.2 A common robotics sensing problem is to place sensors to robustly monitor a set of assets, where robustness is assured by requiring asset $p$ to be monitored by at least $κ(p)$ sensors. Given $n$ assets that must be observed by $m$ sensors, each with a disk-shaped sensing region, where should the sensors be placed to minimize the total area observed? We provide and analyze a fast heuristic for this problem. We then use the heuristic to initialize an exact Integer Programming solution. Subsequently, we enforce separation constraints between the sensors by modifying the integer program formulation and by changing the disk candidate set. |
| title | Multi-Covering a Point Set by $m$ Disks with Minimum Total Area |
| topic | Robotics Computational Geometry F.2.2 |
| url | https://arxiv.org/abs/2502.13773 |