Robustly Guarding Polygons
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929281376976896 |
|---|---|
| author | Das, Rathish Filtser, Omrit Katz, Matthew J. Mitchell, Joseph S. B. |
| author_facet | Das, Rathish Filtser, Omrit Katz, Matthew J. Mitchell, Joseph S. B. |
| contents | We propose precise notions of what it means to guard a domain "robustly", under a variety of models. While approximation algorithms for minimizing the number of (precise) point guards in a polygon is a notoriously challenging area of investigation, we show that imposing various degrees of robustness on the notion of visibility coverage leads to a more tractable (and realistic) problem for which we can provide approximation algorithms with constant factor guarantees. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_11861 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Robustly Guarding Polygons Das, Rathish Filtser, Omrit Katz, Matthew J. Mitchell, Joseph S. B. Computational Geometry We propose precise notions of what it means to guard a domain "robustly", under a variety of models. While approximation algorithms for minimizing the number of (precise) point guards in a polygon is a notoriously challenging area of investigation, we show that imposing various degrees of robustness on the notion of visibility coverage leads to a more tractable (and realistic) problem for which we can provide approximation algorithms with constant factor guarantees. |
| title | Robustly Guarding Polygons |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2403.11861 |