New bounds on guarding problems for orthogonal polygons in the plane using vertex guards with halfplane vision. (English) Zbl 1517.68403
Summary: Given a set \(F\) of \(k\) disjoint monotone orthogonal polygons with a total of \(m\) vertices, we present bounds on the number of vertex guards required to guard the free space and the boundaries of the polygons in \(F\) when the range of vision of each guard is bounded by \(180^\circ \) (the region in front of the guard). When the orthogonal polygons are axis aligned we prove that \(\frac{ m}{ 2} + \lfloor \frac{ k}{ 4} \rfloor + 4\) vertex guards are always sufficient. When the orthogonal polygons are arbitrary oriented, we show that \(\frac{ m}{ 2} + k + 1\) vertex guards are sometimes necessary and conjecture the bound is tight.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
References:
| [1] | Abello, James; Estivill-Castro, Vladimir; Shermer, Thomas; Urrutia, Jorge, Illumination of orthogonal polygons with orthogonal floodlights, Int. J. Comput. Geom. Appl., 8, 01, 25-38 (1998) · Zbl 0957.68117 |
| [2] | Alok Aggarwal, The art gallery theorem: its variations, applications and algorithmic aspects, 1984. |
| [3] | Chvatal, Vasek, A combinatorial theorem in plane geometry, J. Comb. Theory, Ser. B, 18, 1, 39-41 (1975) · Zbl 0278.05028 |
| [4] | Daescu, Ovidiu; Malik, Hemant, City guarding with limited field of view, (Proc. of 32nd Canadian Conf. on Computational Geometry (2020)) |
| [5] | Fisk, Steve, A short proof of Chvátal’s watchman theorem, J. Comb. Theory, Ser. B, 24, 374 (1978) · Zbl 0376.05018 |
| [6] | Hoffmann, Frank; Kriegel, Klaus, A graph-coloring result and its consequences for polygon-guarding problems, SIAM J. Discrete Math., 9, 2, 210-224 (1996) · Zbl 0852.05049 |
| [7] | Kahn, Jeff; Klawe, Maria; Kleitman, Daniel, Traditional galleries require fewer watchmen, SIAM J. Algebraic Discrete Methods, 4, 2, 194-206 (1983) · Zbl 0533.05021 |
| [8] | T.S. Michael, Val Pinciu, Guarding orthogonal polygons with h holes: a bound independent of h. · Zbl 1278.05175 |
| [9] | O’Rourke, Joseph, An alternate proof of the rectilinear art gallery theorem, J. Geom., 21, 1, 118-130 (1983) · Zbl 0542.51020 |
| [10] | O’Rourke, Joseph, Galleries need fewer mobile guards: a variation on Chvátal’s theorem, Geom. Dedic., 14, 3, 273-283 (1983) · Zbl 0516.05018 |
| [11] | O’Rourke, Joseph, Art Gallery Theorems and Algorithms, vol. 57 (1987), Oxford University Press: Oxford University Press Oxford · Zbl 0653.52001 |
| [12] | F. Santos, 1995, personal communication. |
| [13] | Shermer, Thomas C., Recent results in art galleries, Proc. IEEE, 80, 1384 (1992) |
| [14] | Fejes Tóth, L., Illumination of convex discs, Acta Math. Hung., 29, 3-4, 355-360 (1977) · Zbl 0371.52005 |
| [15] | Jorge Urrutia, Art gallery and illumination problems, 2004. · Zbl 0941.68138 |
| [16] | Żyliński, Paweł, Orthogonal art galleries with holes: a coloring proof of Aggarwal’s theorem, Electron. J. Comb., 13, 1, 20 (2006) · Zbl 1087.05020 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
