Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Art gallery problem
Summary
The art gallery problem or museum problem is a well-studied visibility problem in computational geometry. It originates from the following real-world problem:
In the geometric version of the problem, the layout of the art gallery is represented by a simple polygon and each guard is represented by a point in the polygon. A set of points is said to guard a polygon if, for every point in the polygon, there is some such that the line segment between and does not leave the polygon.
The art gallery problem can be applied in several domains such as in robotics, when artificial intelligences (AI) need to execute movements depending on their surroundings. Other domains, where this problem is applied, are in , lighting problems of a stage or installation of infrastructures for the warning of natural disasters.
There are numerous variations of the original problem that are also referred to as the art gallery problem. In some versions guards are restricted to the perimeter, or even to the vertices of the polygon. Some versions require only the perimeter or a subset of the perimeter to be guarded.
Solving the version in which guards must be placed on vertices and only vertices need to be guarded is equivalent to solving the dominating set problem on the visibility graph of the polygon.
Chvátal's art gallery theorem, named after Václav Chvátal, gives an upper bound on the minimal number of guards. It states:
The question about how many vertices/watchmen/guards were needed, was posed to Chvátal by Victor Klee in 1973. Chvátal proved it shortly thereafter. Chvátal's proof was later simplified by Steve Fisk, via a 3-coloring argument. Chvátal has a more geometrical approach, whereas Fisk uses well-known results from Graph theory.
Steve Fisk's proof is so short and elegant that it was chosen for inclusion in Proofs from THE BOOK.
The proof goes as follows:
First, the polygon is triangulated (without adding extra vertices), which is possible, because the existence of triangulations is proven under certain verified conditions.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related lectures (1)
Related people (2)