Example of NP-complete problem

THE ART GALLERY PROBLEM


 The art gallery problem or museum problem is a well-studied visibility problem in computational geometry. It originates from a real-world problem of guarding an art gallery with the minimum number of guards who together can observe the whole gallery. In the computational geometry 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.

Two dimensions

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.

Computational complexity

In decision problem versions of the art gallery problem, one is given as input both a polygon and a number k, and must determine whether the polygon can be guarded with k or fewer guards. This problem and all of its standard variations (such as restricting the guard locations to vertices or edges of the polygon) are NP-hard Regarding approxiamation algorithms for the minimum number of guards, Eidenbenz, Stamm & Widmayer (2001) proved the problem to be APX-hard, implying that it is unlikely that any approximation ratio better than some fixed constant can be achieved by a polynomial time approximatin algorithm.However, a constant approximation ratio is not known. Instead, a logarithemic approximation may be achieved for the minimum number of vertex guards by reducing the problem to a set cover problem. As valtr showed, the set system derived from an art gallery problem has bounded VC dimension, allowing the application of set cover algorithms based on ε-nets whose approximation ratio is the logarithm of the optimal number of guards rather than of the number of polygon vertices. For unrestricted guards, the infinite number of potential guard positions makes the problem even more difficult.

However, efficient algorithms are known for finding a set of at most vertex guards, matching Chvátal's upper bound. David Avis and Godfried Toussaint (1981) proved that a placement for these guards may be computed in O(n log n) time in the worst case, via a divide and conquer algorithm. Kooshesh & Moret (1992) gave a linear time algorithm by using Fisk's short proof and Bernard Chazelle's linear time plane triangulation algorithm.

Fisk's short proof                   

A 3-coloring of the vertices of a triangulated polygon. The blue vertices form a set of three guards, as few as is guaranteed by the art gallery theorem. However, this set is not optimal: the same polygon can be guarded by only two guards.

Fisk(1978)proves the art gallery theorem as follows.

First, the polygon istriangulated (without adding extra vertices). The vertices of the polygon are then 3-colored in such a way that every triangle has all three colors. To find a 3-coloring, it is helpful to observe that the dual graph to the triangulation (the undirected graph having one vertex per triangle and one edge per pair of adjacent triangles) is a tree ,for any cycle in the dual graph would form the boundary of a hole in the polygon, contrary to the assumption that it has no holes. Whenever there is more than one triangle, the dual graph (like any tree) must have a vertex with only one neighbor, corresponding to a triangle that is adjacent to other triangles along only one of its sides. The simpler polygon formed by removing this triangle has a 3-coloring by mathematical induction, and this coloring is easily extended to the one additional vertex of the removed triangle.

Once a 3-coloring is found, the vertices with any one color form a valid guard set, because every triangle of the polygon is guarded by its vertex with that color. Since the three colors partition the n vertices of the polygon, the color with the fewest vertices forms a valid guard set with at most guards.

Three dimensions

An example of a polyhedron with interior points not visible from any vertex.

If a museum is represented in three dimensions as a polyhedron,then putting a guard at each vertex will not ensure that all of the museum is under observation. Although all of the surface of the polyhedron would be surveyed, for some polyhedra there are points in the interior which might not be under surveillance.