A tight bound for point guards in piecewise convex art galleries (Q2391541): Difference between revisions

The paper deals with a piecewise convex art gallery problem which is a generalization of the classical art gallery problem. In this type of art gallery problems, we have a set \(A\) of \(n\) vertices which is a simply connected region in the plane whose boundary consists of \(n\) convex arcs where \(A\) lies on the convex side of each arc. The problem is to find a minimum set \(G \subset A\) of guards that jointly monitor \(A\). The main result of the paper is a theorem which states that every piecewise convex art gallery problem with \(n \geq 1\) vertices can be monitored by at most \(\lceil {n \over 2} \rceil\) point guards (guards positioned anywhere in \(A\)). The proof of the theorem is based on a convex decomposition of the piecewise convex art gallery with \(n\) vertices into at most \(n+1\) convex cells. The set of convex cells is partitioned into at most \(\lceil {n \over 2} \rceil\) subsets. Each of the subsets can be monitored by a single guard lying on a common boundary of the subsets. Before the authors prove the theorem, they give some definitions and lemmas which are needed in the proof. They start with the definition of a convex decomposition of a curvilinear art gallery, a dual graph of a convex decomposition and give a construction of the so-called straightforward convex decomposition. Next, the authors give a definition of a nice decomposition and prove a lemma (Lemma 4) which is used in the proof of the main theorem and which states that every piecewise convex gallery with \(n \geq 2\) vertices has a nice decomposition. The proof of the lemma gives a construction of the nice decomposition. The authors also study the dual graph of the nice decomposition. Then, they prove a lemma (Lemma 11) which states that a curvilinear art gallery with \(n \geq 2\) vertices and a nice decomposition can be monitored by \(\lceil {n \over 2} \rceil\) point guards. The proof of the lemma is a constructive one, it gives a method of finding the point guards. Using Lemmas 4 and 11, the authors give a short proof of the main theorem. Finally, they present a simpler proof of a theorem given by \textit{M. I. Karavelas, C. D. Tóth} and \textit{E. P. Tsigaridas} [Comput. Geom. 42, No. 6--7, 522--535 (2009; Zbl 1169.65019)].