Contiguous Boundary Guarding
Ahmad Biniaz, Anil Maheshwari, Joseph S. B. Mitchell, Saeed Odak, Valentin Polishchuk, Thomas Shermer · 2024
Read Contiguous Boundary Guarding by Ahmad Biniaz, Anil Maheshwari, Joseph S. B. Mitchell, Saeed Odak, Valentin Polishchuk, Thomas Shermer (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-15053.txt.
Introduction
Guarding a border with the fewest watchers is a classic puzzle. Ahmad Biniaz, Anil Maheshwari, Joseph Mitchell, Saeed Odak, Valentin Polishchuk, and Thomas Shermer add a rule: each guard must watch one unbroken stretch of the boundary. They give a simple greedy method that never uses more than one guard beyond the best possible count. Then they give a method that always finds the true minimum.
That exact method is notable because guarding problems are usually too hard to solve exactly in fast time. The team also proves a cap: any polygon with a given number of corners can be guarded by at most a set count of watchers. Some shapes truly need that many. The bound is tight.
Catalog record
| CREATOR | Ahmad Biniaz, Anil Maheshwari, Joseph S. B. Mitchell, Saeed Odak, Valentin Polishchuk, Thomas Shermer |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 53 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-15053
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Contiguous Boundary Guarding Ahmad Biniaz, Anil Maheshwari, Joseph S. B. Mitchell, Saeed Odak, Valentin Polishchuk, Thomas Shermer Abstract 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 \mathrm{OPT}+1 , where OPT \mathrm{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 n -vertex polygon can be guarded by at most ⌊ n − 2 2 ⌋ \lfloor\frac{n-2}{2}\rfloor guards. This bound is tight because there are polygons that require this many guards. 1 Introduction The art gallery problem , introduced in 1973 by Victor Klee [ 15 , 40 ] , asks for a minimum number of guards that see every point of a given polygon P ---the guards can lie anywhere in the polygon. 1 1 1 It is also known as the point-guard art gallery problem. This problem is central to computational geometry and is still an active research area. It has been long known NP-hard [ 35 ] ; see also [ 3 , 40 , 42 ] . The recent breakthrough result by Abrahamsen, Adamaszek, and Miltzow [ 1 ] shows that the problem is \exists\mathbb{R} -complete 2 2 2 \exists\mathbb{R} consists of all problems reducible to the decision problem for the existential theory of the reals. even if the corners of the polygon are at integer coordinates. The problem is notoriously difficult as the best known approximation algorithms have logarithmic factors [ 12 , 19 , 20 ] ; see also [ 21 ] for some lower bounds on the approximation factor. The boundary guarding is a variant of the art gallery problem in which the goal is to guard only the boundary of P with a minimum number of guards that can lie anywhere in P . One may think of this as guarding only the walls of an art gallery with no sculptures. By extending ideas of [ 1 ] , Stade has shown that this variant is also \exists\mathbb{R} -complete [ 47 ] . We introduce the contiguous version of this problem. In the contiguous boundary guarding problem, the goal is to guard the boundary of P such that each guard covers a contiguous portion of the boundary. While the visibility polygon of a guard may have several connected components when intersected with the boundary, the guard is assigned to only one component. Contiguous boundary guarding is natural, particularly if the guards have a bounded field of view or cannot rotate to cover all visible components on the boundary. This problem appeared in Open Problems from CCCG 2024 [ 4 ] , motivated by the fact that the hardness proofs for typical art gallery variants [ 1 , 47 ] require guards to cover several connected components on the boundary. In this paper, we present an exact polynomial-time algorithm and tight combinatorial bounds for the contiguous boundary guarding problem. 1.1 Our results We study the contiguous boundary guarding problem from combinatorial and computational points of view. In Section 2 we give a constructive proof that for every integer n\geq 4 , every n -vertex polygon can be guarded by at most \lfloor\frac{n-2}{2}\rfloor guards. This bound is the best possible as some polygons require this many guards. In Section 4 we present a simple greedy algorithm that returns a guard set of size at most \mathrm{OPT}+1 , where \mathrm{OPT} is the number of guards in an optimal solution. 3 3 3 A similar greedy algorithm has been used in [ 2 ] for some covering problems. The algorithm starts from an arbitrary point p on the boundary and then covers the boundary in a counter-clockwise (ccw) direction from p . It places a guard to cover p and a maximal contiguous portion of the boundary in the ccw direction. The algorithm then continues greedily, covering a maximal contiguous boundary portion with each choice of guard, until returning to p . Despite getting very close to optimal by this greedy algorithm, achieving an optimal solution (avoiding an extra guard) is challenging. An interesting property of the greedy algorithm is that if p is covered by two guards in some optimal solution, then the greedy algorithm returns a guard set of size \mathrm{OPT} . In Section 5 we present a polynomial-time exact algorithm for the problem. This algorithm is not complicated, though its correctness proof (presented in Section 6 ) involves some nontrivial arguments. The main idea is first to find a polynomial-size set S of points on the boundary such that at least one of them is covered by two guards in some optimal solution. Then, we find an optimal solution by running the greedy algorithm from every point in S . Finding such a set S is the most technical part of the algorithm and the proof. 1.2 Related work and results The art gallery problem and its variants have been extensively studied. Most of the variants (that arise from enforcing constraints, say, on the input polygon, on the location of the guards, or on the portion of the polygon to be guarded) remain NP-hard. Hardness and approximations The vertex-guard problem is a discrete version of the art gallery problem where the guards must be located at the vertices of the polygon. This version is also NP-hard [ 35 , 42 ] with known logarithmic factor [ 26 ] and sub-logarithmic factor [ 31 ] approximation algorithms. A similar sub-logarithmic approximation is known for the case where the guards can lie anywhere on the boundary of the polygon [ 31 ] . Better approximation algorithms are known for monotone polygons [ 33 ] and weakly-visible polygons [ 5 , 9 ] . Terrain guarding is a related problem in which we are given a 1.5-dimensional terrain (i.e., an x -monotone polygonal chain), and the goal is to find a minimum number of guards on the terrain that guards the terrain—this is a variant of the boundary guarding problem. This problem is also NP-hard [ 14 , 32 ] , and admits polynomial time approximation scheme [ 5 , 27 ] . Both versions of the problem (point-guard and vertex-guard) remain NP-hard in orthogonal polygons 4 4 4 Also known as rectilinear polygons. [ 45 ] . Even if we want to guard only the vertices of an orthogonal polygon, the problem is still NP-hard [ 30 ] for three versions where the guards lie on vertices, on the boundary, or anywhere in the polygon. Polynomial-time exact algorithms For some trivial instances, the art gallery problem can be solved in polynomial time, such as for convex, star-shaped, and spiral polygons. Finding non-trivial instances that