Fast vertex guarding for polygons with and without holes
In the [Proceedings of the Canadian Information Processing Society Congress, 429-434 (1987)], \textit{S. K. Ghosh} introduced approximation algorithm for art gallery problems (i.e., polygon guarding problems). \textit{P. Bose} et al., [Comput. Geom. 23, No.3, 313--335 (2002; Zbl 1019.65020)], studied efficient visibility queries in simple polygons and introduced a minimum decomposition with fewer cells. The author mainly focuses on generalizing the foregoing work of Bose et al. on simple polygons, to polygons with holes. Algorithms with faster running times and improved approximation factor have been presented.
scientific article; zbMATH DE number 6130519