Calculating an (OPT+1)-arrangement of guards, restricted to the boundary of a circle, covering an enclosed polygon.
(Please click on the button above to start the applet.)
The objective is to gaplessly watch the outward appearance of a simple polygon by placing a minimal number of guards into its environment. (We call this the Minimum Fortress Guard Problem (MFGP).) By reduction from the well known Minimum Art Gallery Problem (MAGP) it can be easily shown that MFGP is NP-complete. That's why Isler, Kannan and Daniilidis introduced some restrictions for being able to find a practical approximation for this (see [IKD01] and [Jun05]). One of these approaches is called
Guards may be exclusively placed on the boundary of a circle which contains the complete polygon. The authors invented an algorithm (PlaceGuards) which computes an approximation for MFGP that needs at most one more guard than OPT would use under the same requirements and terminates within a polynomial amount of time.
The analysis models 2DCircle as an instance of SetCover which is then transformed to
one-dimensional HittingSet. The resulting IntervalHittingSet can be solved by a
suitable Sweep-Algorithm in polynomial time and produces - in the linear case!! - an optimal solution (OPT)
for the given problem.
2DCircle may need one additional guard, because for the transformation to the linear case, the radial arcs have to be sliced once at some angle, so that some of the radial intervals (arcs) are cut into two pieces.
Each vertex of the given polygon is associated with a so called Visibility Arc which begins at the angle in which the corresponding vertex appears and ends at the angle in which it disappears. These arcs represent the intervals for the IntervalHittingSet, mentioned above. While sweeping clockwise around the circle, a guard will be placed each time an as yet uncovered Visibility Arc reaches its end.
The Algorithm PlaceGuards
For easier understanding we skip the initial steps of the algorithm and start somewhere later in its main-loop:
The algorithm maintains a list Q_A of currently uncovered Visibility Arcs.
For placing the next guard, it picks the arc with the nearest endpoint from this list and
places the new guard at its endpoint.
For the following analysis let g be the number of guards placed by the algorithm and n the number of vertices of the original input polygon.
Now it uses some nifty approach for being able to compute all segments of the polygon boundary,
visible from the new guard positon, in time O(n*g):
First it computes some kind of inverse polygon which consists of the whole chain of polygonal edges from the side of the polygon which is faces the new guard position and including the new guard position itself. In this inverse polygon the Visibility Polygon is computed by making use of the linear time algorithm, invented bei D. T. Lee, which can be found in [Kle05] (pages 182-190). Using this Visibility Polygon, it computes the parts of the boundary, visible from the new guard position and adds them to a list called Covered. (The algorithmus maintains an extended version of the input polygon which includes the endpoints of all these segments yet seen as additional vertices. This makes the graphical appearance some more pretty and is used for some internal algorithmic compuations...)
After this step, the algorithm inspects the continuity of all segments, covered by all currently placed
guards and computes the Visibility Arcs of the endpoints of each of these chains:
The algorithm performs an intersection test for the rays, starting at the given point on the polygon boundary and passing all the other polygon vertices. With the aid of suitable epsilon-neighborhoods, it finally computes the two rays which deliminate the visibility cone. Their intersections with the surrounding circle mark the endpoints of the searched associated Visibility Arc. The whole task takes time O(n).
Afterwards it needs time O(n*g) for fitting the computed arc to the assumption, that polygonal edges are open (means: One cannot look beyond the horizon of the elongated edge (important for convex vertices!).)
In combination the computation of one single Visibility Arc takes time O(n(n+g)).
The maintenance of the list Covered, including the check of the termination condition, is still some kind of naïve and takes time O((n*g)^2). If one was able to lower the above upper bound for the computation of an Visibility Arc, it might be worth dealing with more efficient approaches for these tasks.
After the whole polygon boundary has been covered, the algorithm will terminate.
The start button above opens a separate frame, containing the actual application.
What you need to do is the following:
|Draw the polygon, which shall be covered. (left mouse button)|
|Open a popup menu for placing the center of the circle which the algorithm will use for placing the guards. (right mouse button)|
|The midpoint (and later: the whole circle) can be moved by dragging its center point. (left mouse button)|
|Draw the circle by dragging from its midpoint (right mouse button). It can resized by dragging its boundary.|
|Click the "GO" button to start the algorithm.|
The animation speed can be modified by moving the slider.
It pauses when clicking "PAUSE" and continues after clicking "GO" or alternatively ">".
The current task and each placed guard is listed in the textbox on the right hand side.
|After activating the checkbox "single-step mode", the buttons "<" and ">" are used for stepwise navigation backward or forward through the animation.|
note: Even if you activate the single-step mode before starting the algorithm, you have to click "GO" once at first!
|The algorithm has terminated by the time it says "DONE!" in the textbox. You can now click "Reset" for going back to the beginning and maybe modifying the scene.|
|The violet colored arcs represent the Visibility Arcs, mentioned above. Their endpoints are marked by a tiny dot.|
The current viewpoint is marked by a small red unfilled circle, situated on the boundary of the huge circle.
Looking at the polygons, the grey-filled one is the unmodified input polygon. The green one is the extended polygon. The polygon with a brown filling is the inverse polygon, calculated by the algorithm. The golden yellow colored one, is the visibility polygon of the new guard inside the inverse polygon. (Later, the corresponding, visible polygon segments will be drawn in the same color...)
|After the algorithm has finished, it has placed the dark-filled dots which represent the necessary guard-positions.|
|[IKD01]||Isler, V., S. Kannan and K. Daniilidis: VC-Dimension of Exterior Visibility of Polyhedra. Technical report MS-CIS-01-34, Computer and Information Science, University of Pennsylvania, 2001.|
|[Jun05]||Jung, Daniel: Minimum Fortress Guard Problem and VC-Dimension. Seminar paper, based on [IKD01], University of Bonn, 2005.|
|[Kle05]||Klein, Rolf: Algorithmische Geometrie - Grundlagen, Methoden, Anwendungen. Springer, Heidelberg 2nd Edition, 2005.|