×

Finding minimum witness sets in orthogonal polygons. (English) Zbl 1477.68456

Summary: A witness set W in a polygon \(P\) is a subset of \(P\) such that any set \(G \subset P\) that guards \(W\) is guaranteed to guard \(P\). We study the problem of finding a minimum witness set for an orthogonal polygon under three models of orthogonal visibility. It is known that not all simple polygons admit a finite witness set under the traditional line-segment visibility and, if a polygon admits a finite minimal witness set, then the witnesses must lie on the boundary of the polygon [K.-Y. Chwa et al., Lect. Notes Comput. Sci. 3341, 352–363 (2004; Zbl 1116.68618); Int. J. Comput. Geom. Appl. 16, No. 2–3, 205–226 (2006; Zbl 1090.65069)]. In this paper, we prove that every orthogonal polygon with \(n\) vertices admits a finite witness set with \(O( n^2)\) witnesses under rectangular, staircase, and \(k\)-periscope visibility. This upper bound is tight under staircase visibility. We also show an orthogonal polygon whose boundary is not a witness set for any of the three considered visibility models. We finally describe how to find a minimum witness set for a given orthogonal polygon in \(O( n^4)\) time under rectangular and staircase visibility, and in \(O( n^6)\) time under \(k\)-periscope visibility.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abrahamsen, M.; Adamaszek, A.; Miltzow, T., The art gallery problem is \(\exists \mathbb{R} \)-complete, (Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018 (2018), ACM), 65-73 · Zbl 1427.68324
[2] Bärtschi, A.; Suri, S., Conflict-free chromatic art gallery coverage, Algorithmica, 68, 1, 265-283 (2014) · Zbl 1286.68460
[3] Biedl, T. C.; Mehrabi, S., On r-guarding thin orthogonal polygons, (27th International Symposium on Algorithms and Computation. 27th International Symposium on Algorithms and Computation, ISAAC 2016. 27th International Symposium on Algorithms and Computation. 27th International Symposium on Algorithms and Computation, ISAAC 2016, Leibniz International Proceedings in Informatics (LIPIcs), vol. 64 (2016), Schloss Dagstuhl-Leibniz-Zentrum Fuer Informatik: Schloss Dagstuhl-Leibniz-Zentrum Fuer Informatik Dagstuhl, Germany), Article 17 pp. · Zbl 1398.68614
[4] Chvàtal, V., A combinatorial theorem in plane geometry, J. Comb. Theory, 18, 1, 39-41 (1975) · Zbl 0278.05028
[5] Chwa, K.-Y.; Jo, B.-C.; Knauer, C.; Moet, E.; van Oostrum, R.; Shin, C.-S., Guarding art galleries by guarding witnesses, (Fleischer, R.; Trippen, G., Algorithms and Computation (2005), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 352-363 · Zbl 1116.68618
[6] Eidenbenz, S.; Stamm, C.; Widmayer, P., Inapproximability results for guarding polygons and terrains, Algorithmica, 31, 1, 79-113 (2001) · Zbl 0980.68140
[7] Fink, E.; Wood, D., Restricted-Orientation Convexity (2012), Springer Science & Business Media
[8] Fisk, S., A short proof of Chvàtal’s Watchman theorem, J. Comb. Theory, Ser. B, 24, 374 (1978) · Zbl 0376.05018
[9] Gewali, L., Recognizing s-star polygons, Pattern Recognit., 28, 7, 1019-1032 (1995)
[10] Gewali, L.; Ntafos, S., Covering grids and orthogonal polygons with periscope guards, Comput. Geom., 2, 6, 309-334 (1992) · Zbl 0774.68058
[11] Lee, D.; Lin, A. K., Computational complexity of art gallery problems, IEEE Trans. Inf. Theory, 32, 2, 276-282 (1986) · Zbl 0593.68035
[12] Motwani, R.; Raghunathan, A.; Saran, H., Covering orthogonal polygons with star polygons: the perfect graph approach, J. Comput. Syst. Sci., 40, 1, 19-48 (1990) · Zbl 0705.68082
[13] O’Rourke, J., Art Gallery Theorems and Algorithms (1987), Oxford University Press, Inc.: Oxford University Press, Inc. New York, NY, USA · Zbl 0653.52001
[14] Schuchardt, D.; Hecker, H.-D., Two NP-hard art-gallery problems for ortho-polygons, Math. Log. Q., 41, 2, 261-267 (1995) · Zbl 0827.68115
[15] Schuierer, S.; Wood, D., Staircase visibility and computation of kernels, Algorithmica, 14, 1, 1-26 (1995) · Zbl 0837.68119
[16] Shermer, T. C., Recent results in art galleries (geometry), Proc. IEEE, 80, 9, 1384-1399 (1992)
[17] Urrutia, J., Art gallery and illumination problems, (Sack, J.-R.; Urrutia, J., Handbook of Computational Geometry (2000), North-Holland), 933-1027 · Zbl 0941.68138
[18] Worman, C.; Keil, J. M., Polygon decomposition and the orthogonal art gallery problem, Int. J. Comput. Geom. Appl., 17, 02, 105-138 (2007) · Zbl 1144.65015
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.