Title :
The art gallery theorem for polygons with holes
Author :
Hoffmann, Frank ; Kaufmann, Michael ; Kriegel, Klaus
Author_Institution :
Karl-Weierstrass-Inst. fur Math., Berlin, Germany
Abstract :
Art gallery problems which have been extensively studied over the last decade ask how to station a small (minimum) set of guards in a polygon such that every point of the polygon is watched by at least one guard. The graph-theoretic formulation and solution to the gallery problem for polygons in standard form is given. A complexity analysis is carried out, and open problems are discussed
Keywords :
computational geometry; art gallery theorem; complexity analysis; graph-theoretic formulation; open problems; polygons with holes; Algorithm design and analysis; Art; Shape; Subspace constraints; Upper bound; Watches;
Conference_Titel :
Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium on
Conference_Location :
San Juan
Print_ISBN :
0-8186-2445-0
DOI :
10.1109/SFCS.1991.185346
