An implementation of a Heuristic for the Orthogonal Art Gallery Problem
George E. Antoniou · Language arts journal of Michigan · 2005
The Art Gallery Problem is a classical problem in Computational Geometry: Given an Art Gallery, what is the minimum number of guards and their locations so that they can watch the entire Gallery? The problem can be restated in terms of illumination and lights. An interesting version of the original problem arises when two additional condition are imposed: 1. All the walls of the Art Gallery form square angles (Orthogonal polygon) 2. The guards can be placed only on the corners of the Gallery This particular version of the problem has been shown to be NP-hard.