Fast vertex guarding for polygons with and without holes
type: Item
instance of: scholarly article
title: Fast vertex guarding for polygons with and without holes
zbMATH Open document ID: 1262.65032
author: Yanyan Li
published in: Computational Geometry
publication date: 2013-01-25T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 65D18
zbMATH DE Number: 6130519
zbMATH Keywords: art gallery problem
zbMATH Keywords: vertex guarding
zbMATH Keywords: approximation algorithms
zbMATH Keywords: visibility decomposition
reviewed by: H. P. Dikshit
MaRDI profile type: Publication
full work available at URL: j.comgeo.2012.07.004
OpenAlex ID: W2017822593
DOI: 10.1016/J.COMGEO.2012.07.004
description: scientific article; zbMATH DE number 6130519