Art gallery problem

The problem of the museum guard (s: Art gallery problem) is a question of computational geometry. The following situation is examined:

" Given a polygonal surface with boundary, interpreted as the floor plan of a museum. Now choose the smallest possible number of points ( " Guardian " ) inside the polygon such that any point in the interior of the polygon can be connected by a straight line that lies entirely in including edge with a guard. "

This is equivalent to a minimal polygon to cover star-shaped.

In practice, the problem in robotics occurs when " artificial intelligence " to perform movement patterns depending on their environments. Some issues of digital image processing can be traced back to guard problems. Also lighting problems a stage and the problem with the observation of animal populations in large areas can be modeled as a guard problem. Another application is the preparation of the infrastructure for weather observation or for warning of natural disasters.

The problem falls into the class of computationally APX - problems, that is, that probably [A 1], no algorithm exists that solves it efficiently and correctly for general polygons. On the other hand, it has been found to the problem and its variants upper bounds for the number of guards and can prove that they are also sharp. That is, they can not be further improved without having to restrict to specific polygon classes.

Probably the first systematic consideration of visibility issues suggested Victor Klee in August 1973 at a conference at Stanford on by formulating the museum problem for point guards and is exposed as a correct guess. Two years later Chvátal presented a proven solution to the problem.

Elementary Examples

We first consider the "simple" version of the problem with stationary guards. You wonder for a predetermined small number of edges a polygon that requires as many guards. In a triangle and a square one has few opportunities because obviously always a sufficient guard. For a pentagon that is still correct, this insight is not so obvious:

• Special case of 5 -sided polygons

Figure 2

Figure 3

Figure 4

The first three pictures show stereotype of all possible pentagons: each pentagon can either none, one, or have two concave corners, so the corners have an internal angle greater than 180 °, or in radians. This follows from the fact that in each corner the sum of the interior angles is equal in the case of this total. So you can be at most two concave corners.

For the fourth example, you would need two guards: one on one of the contact points of the triangles and another in each remaining triangle. However, you would there complain that the polygon has "actually" nine pages, if you want to prohibit duplication. One usually does. From now on, only those schneidungsfreien polygons are considered.

• More "critical graphs" for small ridge counts

Figure 6

Figure 7

Figure 8

In the case (Figures 5 and 6), the result would be that polygons exist that can not be guarded by a guard alone, but always rich two guards from. Performs one such considerations continue, one can observe that after three other edges, another guard may be necessary. A polygon that requires a maximum number of guards to a number of edges are called in the context of the problem is a critical polygon.

Set of Chvátal

The proof that the above examples are actually critical polygons, so that for nine - or twelve -edged polygons are always sufficient three respectively four guards, is a special case of the following theorem:

" For the security of each non-overlapping, closed, planar polygon with sides [A 2] Guardian points always sufficient and sometimes necessary. "

As evidence, there are essentially two versions: A geometric variant as stated Chvátal first, and a graph-theoretic, which was given by S. Fisk. Fisk's proof uses some well- known results from graph theory, so the proof is relatively short and is regarded as something aesthetic. On the other hand, it can be in contrast to Chvátal not to some generalizations.

Before the proof of this theorem was known that this upper bound, if it should turn out to be valid, could not be further tightened. This purpose we consider the following sequence of graphs with edges. Each such polygon requires guards.

In reference to Fisk's proof design developed Avis and Toussaint an algorithm that constructs a guard set of size. His life depends largely on how efficiently a triangulation can be found. Some simple methods to realize that in quadratic time. In their article, they propose a version in front. [A 3] In 1990, Chazelle presented an algorithm with running time.

The coloring is then relatively easily be constructed by assuming that the triangulation passes a data structure that contains all Adjazenzinformationen. Generally can not be secured. The performance of Toussaint and Avis was to find a coloring in linear time, alone under the use of a list of tendon edges of the triangulation.

Variants and generalizations

Orthogonal polygons

An important special case of the Guardian problem is the restriction to orthogonal polygons. [A 4] This refers to polygons, receiving only the interior angle and the 90 ° and 270 °. Such polygons are considered in geometric applications that are strongly bound to the Cartesian coordinate system: this includes design problems of highly integrated circuits, architecture and some algorithms on raster graphics.

The first obvious assumption that with this restriction, a better bound on the number of required guards would be able to prove it was confirmed in 1980 by a set of Klawe and Kleitman. They showed the existence of so-called " convex Quadrilaterationen ": [A 5] These are analogous to the triangulation, decompositions of a polygon into convex quadrilaterals by tendons between certain corners are drawn which are entirely in the polygon. Their evidence for this is very general also holds for a corresponding statement about polygons with ( finitely many ) " holes" or " overlaps ". [A 6] It can be shown relatively easily that the dual graph of a convex Quadrilateration not the Kuratowskiminoren, so and may include the graph. By the theorem of Kuratowski the graph is planar and then vierfärbbar after Vierfarbentheorem. It follows the sentence:

" For the security of each center be - and hole-free and planar and orthogonal polygon with sides Guardian points always sufficient and sometimes necessary. "

That guards are sometimes necessary, is analogous to the example of the general case of " orthogonal comb":

To show the existence of the convex Quadrilaterationen, the proof uses the following concepts build on each other:

A "right" and "left" edge and a polygon are called adjacent if

It follows immediately that an edge no neighbor must exist, but if one exists so without loss of generality can be assumed that this is clear. [A 7] If two adjacent edges connected by a vertical edge, called the three edges together an ear. For "upper" and "lower" edges to define the neighborhood and ear property completely analogous.

In the given polygons to find such ears, so is interesting because it can be proved relatively easily that every convex Quadrilateration must contain each ear. However, one needs to obtain the statement of the Wächtertheorems, grasp the concept more generally, because not every polygon must contain an ear.

In addition, there are those ( ear -containing ) polygons that make it a polygon by cleavage of a convex quadrilateral to one or more smaller, ie, with at least one hole or an edge due less, and those which do not allow such a reduction. This is called reducible respectively irreducible. Klawe and Kleitmann could show that orthogonal polygons

• Either in this sense are reducible
• Or a pair of ears ( two ears, so that the connecting edges of the adjacent edges see each other ) contain,
• Contain or two adjacent edges that do not form an ear,
• Must have or infinitely many corners.

In the case of the ear pair and the adjacent edges they could also indicate a reduction to a smaller polygon and so inductively justify the existence of the proposed Quadrilaterationen for finite polygons.

• Examples of convex Quadrilaterationen

The square is an ear. No ear because with adjacent. The in this case unique convex Quadrilateration ( drawn) can not be constructed from a general triangulation. (which might include the triangle )

Algorithms

An attempt to apply the newly presented evidence is blind in front of his doctoral thesis of 1984.

Another proof approach and a derived algorithm Lubiw 1985 has developed.

Fortress problem

Derick Wood and Joseph Malkelvitch introduced in the 1970s independently the question of two generalizations of the problem of a museum guard: Instead of finding points that guard the interior of a polygon, they asked for points that guard the exterior, or do both. Wood coined the name fort problem ( for security problems of external fields ) and problems of the prison yard ( for problems in which both had to be guarded ). The fortress problem is solved satisfactorily so far as that sharp statements could be proved to the required number of guards for a polygon in the number of corners.

" To solve the problem fortress corner guards are sometimes necessary and always sufficient"

An example for the need of each convex polygon. That this is sufficient follows from the following construction: For a general polygon, consider the convex hull. Trianguliere now the part of the plane which lies within the convex hull but outside the polygon. Choose a künstchen node and connect all points of the convex hull with it. At any node, the convex hull of the polygon is now " open " is replaced by nodes and up depending on an edge that they connect with their neighbors on the convex hull, identical incidences like. The resulting graph with nodes is a Triangulationsgraph, ie three-colorable. It is expected then from elementary that a minimal chromatic class that does not contain, is at most of order. The transfer of the evidence on the orthogonal case has Argawall carried out and he comes in to the conclusion that corner guards are always sufficient and sometimes necessary. Both proofs provide linear -time algorithms for constructing a corresponding amount guardian.

If one removes the restriction that guards may be placed only at the corners, one can show that it is always sufficient and sometimes necessary. As proof, an idea of Shermer has proved insightful. We construct a Triangulationsgraphen: Two additional points of the polygon chosen sufficiently far away right and left. With the convex hull can then be explained by a graph with nodes for which there exists a triangulation. In the event that the number of nodes on the convex hull is straight, this graph the points on the envelope is then 3 -colorable, the additional nodes get the color one, then alternately two and three. If it is odd, one can accept a trick to another node and is in the straight case. A smallest chromatic class then contains nodes.

Results of the guards Theory Overview

• Notes the number of corners. (Corners of holes are counted if they are available)
• Records the number of the holes, if any. Means no entry.
• Listed the number of concave corners. A corner is called concave if and only if its interior angle is greater than.
• And are the Gaussian or Entierklammern. They round the enclosed expression integer on or off.

More critical examples

• For star-shaped polygons

Proof of the lower bound in the number of concave corners de for star-shaped polygons: For any two prongs you need a guard at the concave corners. No more than two prongs corner.

Idea of ​​proof of the lower bound in the number of corners for Star-shaped polygons: For you need edge guards here. The generalization for more you have to choose the prongs Such pointed that induced by each Pip Pip rays for each cut another edge of the "circle ".

Example of a star-shaped polygon that requires two diagonal guards. Two of the four possible diagonals are drawn: No cuts the gray highlighted core region. This example was from Shermer and Suri discov.

• Barrier in the number of concave corners and polygons with holes.

For corners guards are required. The left polygon goes back to Julian Sidarto. The two rights at Tomas Shermer.

Here you need guards for corners. The Left goes back to Shermer; the rights to Arthur Delcher. This and the previous examples with holes were found in a homework assignment of a seminar of O'Rourke.

And three holes need corner guards.