“Two approximate solutions to the Art Gallery Problem” by Rana
Conference:
Type(s):
Entry Number: 066
Title:
- Two approximate solutions to the Art Gallery Problem
Presenter(s)/Author(s):
Abstract:
The Art Gallery Problem [Chvátal 1975] is a well known NP-hard computational geometry question, where the aim is to find the minimum number of observers required for complete visual coverage of an art gallery. Most existing solutions are based on heuristics that are dependent on the geometry and topology of the gallery i.e. whether the gallery is convex, rectilinear etc.
References:
1. Chvátal, V. 1975. A Combinatorial Theorem in Plane Geometry. Journal of Combinatorial Theory 18, 39–41.
2. Rana, S. and Batty, M. 2004. Visualising the structure of Architectural Open Spaces based on Shape Analysis. International Journal of Architectural Computing 2, 1, 123–132.
