Contiguous Boundary Guarding
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908353378123776 |
|---|---|
| author | Biniaz, Ahmad Maheshwari, Anil Mitchell, Joseph S. B. Odak, Saeed Polishchuk, Valentin Shermer, Thomas |
| author_facet | Biniaz, Ahmad Maheshwari, Anil Mitchell, Joseph S. B. Odak, Saeed Polishchuk, Valentin Shermer, Thomas |
| contents | We study the problem of guarding the boundary of a simple polygon with a minimum number of guards such that each guard covers a contiguous portion of the boundary. First, we present a simple greedy algorithm for this problem that returns a guard set of size at most OPT + 1, where OPT is the number of guards in an optimal solution. Then, we present a polynomial-time exact algorithm. While the algorithm is not complicated, its correctness proof is rather involved. This result is interesting in the sense that guarding problems are typically NP-hard and, in particular, it is NP-hard to minimize the number of guards to see the boundary of a simple polygon, without the contiguous boundary guarding constraint.
From the combinatorial point of view, we show that any $n$-vertex polygon can be guarded by at most $\lfloor \frac{n-2}{2}\rfloor$ guards. This bound is tight because there are polygons that require this many guards. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_15053 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Contiguous Boundary Guarding Biniaz, Ahmad Maheshwari, Anil Mitchell, Joseph S. B. Odak, Saeed Polishchuk, Valentin Shermer, Thomas Computational Geometry We study the problem of guarding the boundary of a simple polygon with a minimum number of guards such that each guard covers a contiguous portion of the boundary. First, we present a simple greedy algorithm for this problem that returns a guard set of size at most OPT + 1, where OPT is the number of guards in an optimal solution. Then, we present a polynomial-time exact algorithm. While the algorithm is not complicated, its correctness proof is rather involved. This result is interesting in the sense that guarding problems are typically NP-hard and, in particular, it is NP-hard to minimize the number of guards to see the boundary of a simple polygon, without the contiguous boundary guarding constraint. From the combinatorial point of view, we show that any $n$-vertex polygon can be guarded by at most $\lfloor \frac{n-2}{2}\rfloor$ guards. This bound is tight because there are polygons that require this many guards. |
| title | Contiguous Boundary Guarding |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2412.15053 |