Proceedings of the IEEE · 1992 · 333 citations · 52 references
ComputingMathematicsCombinatoricsComputational GeometryGeometryGeometric OptimizationLine Segment IntersectionVisibility ComputationVisibility GraphsMinimum Set ProblemPoint VisibilityPolygon Theory
Two points in a polygon are called visible if the straight line segment between them lies entirely inside the polygon. The art gallery problem for a polygon P is to find a minimum set of points G in P such that every point of P is visible from some point of G. This problem has been shown to be NP-hard by Lee and Lin [71]. However, Chvatal showed that the number of points of G will never exceed [n/3] for a simple polygon of n sides [21]. This latter result is referred to as the art gallery theorem
52
Algorithms in Combinatorial Geometry.
Jacob E. Goodman, Herbert Edelsbrunner · American Mathematical Monthly · 1989 · 1.8K citations
Computational complexity of art gallery problems
D. Lee, A. Lin · IEEE Transactions on Information Theory · 1986 · 406 citations