art gallery problem

Thierry Dagnino -- Computational Geometry : "You are the owner of an art gallery and want to place cameras such that the whole gallery will be thief proof.

Where will you place the cameras in a way that the whole gallery is guarded?
How many cameras do you have to buy?
What is the minimum number of cameras required to protect your expensive art collection ?

These are all questions we will answer. The purpose of this page is to familiarize you with the art gallery problem, to demonstrate an algorithm that solves this problem and hopefully to get you interrested in computational geometry problems.

History : The art gallery problem was introduced by Victor Klee in 1973 in a discussion with Vasek Chvatal. There are many forms of the art gallery problem. We will only look at one of them. Some of the others will be mentionned at the end of this document.

Problem : The gallery will be represented by a simple polygon. Cameras are assumed to have a viewport of 360 degrees. Put otherwise they rotate at infinite speed. Moreover they can see as far as nothing is in their way, i.e until there is a wall. We will ignore the size of the cameras and forget about their vertical positioning. Cameras will be represented by points in the region enclosed by the polygon. The camera sees all points it can be connected to by a segment lying entirely inside the polygon.

Find how many cameras are needed to guard the whole polygon, i.e to view every point inside the polygon.

Where should they be positioned ?"