THE a walk of minimum length within time O(n

THE TWO GUARDS PROBLEM
CHRISTIAN ICKING
and
ROLF KLEIN
Praktische Informatik VI, Fernuniversit¨at – GH – Hagen
Elberfelder Str. 95, D-5800 Hagen, Germany
Received 18 June 1991
Revised 18 December 1991
Communicated by D. T. Lee
ABSTRACT
Given a simple polygon in the plane with two distinguished vertices, s and g, is it
possible for two guards to simultaneously walk along the two boundary chains from s to
g in such a way that they are always mutually visible? We decide this question in time
O(n log n) and in linear space, where n is the number of edges of the polygon. Moreover,
we compute a walk of minimum length within time O(n logn + k), where k is the size of
the output, and we prove that this is optimal.
Keywords: visibility, watchman routes, planar polygons, motion planning.
1. Introduction
Several types of watchman problems (also called art gallery problems) have been
proposed in the literature. The first of this family of problems was the minimum
watchmen problem considered by Chvatal1 and Fisk2 and many others, where a
number, as small as possible, of places for watchmen in a given scene is to be
calculated such that every point of the edges (walls) in the scene is visible from
at least one place (watchman). Lee and Lin3 have shown that finding the exact
minimum number of watchmen in a simple polygon is NP-hard.
Another example of this type of problem is the watchman route problem. There,
a route of minimum length within a polygon has to be found such that every point
of the polygon is visible from at least one point of the route. In some circumstances,
this problem is NP-hard, too, see Chin and Ntafos4. A survey of art gallery problems
and many other related issues can be found in O’Rourke5.
In this paper, we study the following problem. Imagine a police patrol in a
dangerous midtown street. Each of two officers has to walk along one of the sidewalks,
all the way down the street, and to check all the bank doors on his side.
Can the two guards proceed in such a way that they are always mutually visible?
1
More formally, let us assume that we are given a simple polygon with n edges and
distinguished vertices s and g. Can two points be moved from s to g, each on one
of the two boundary chains, such that the line segment connecting the two points
is at each time fully contained in the polygon? The points are allowed to backtrack
locally, but eventually they must both arrive at g. A movement subject to these
constraints is called a walk. A polygon that admits a walk is walkable. The general
walk problem asks for a walk in which the total distance travelled by the two points
is minimized.
One special case arises when no backtracking is necessary in order to get the
points from s to g. Such a walk will be called straight. During a straight walk,
the line segment connecting the points sweeps the polygon in an ordered way. In
a sense, this is a generalization of monotone polygons, which can be swept with a
line of fixed orientation. In our problem, the line can turn during the sweep. As
we compute a walk of minimum length, we will find a straight walk, if there is one.
It turns out that the important information for deciding if a straight walk exists
can be extracted from the hit points of the edge extensions of the polygon’s reflex
vertices, see Figure 6. For answering these shooting queries in total time O(n logn),
we employ the method of Chazelle and Guibas6. In Section 3 we show that this
leads to an O(n log n) algorithm that computes a straight walk.
During a walk it may be necessary for one of the guards to move backwards
(towards s) while the other one still advances towards g. This type of motion is
called a counter-walk. In Section 4 we give an O(n log n) algorithm for the straight
counter-walk problem: Can one guard move from s to g while the other one moves
from g to s on the other side without backtracking, in such a way that they are
always mutually visible? In addition to answering shooting queries, here we also
have to compute certain visibilities. To this end, we apply the shortest path algorithm
by Guibas and Hershberger7 in order to compute, for each vertex v, the first
segments of the shortest paths from v to a point on the opposite chain. This can
be done in total time O(n logn).
Section 5 shows how these results can be used to solve the general walk problem,
i.e. to move the guards from s to g with backtracking. We compute in time
O(n logn + k) a minimum length walk, and prove in Section 6 that this is the optimum
bound. Here, k denotes the size of the output, i. e. the number of walk
instructions for the two guards. A single walk instruction causes the guards to walk
straight towards the next halting point, at most to the next vertex in the given direction.
Hence, the number k of walk instructions is not less than the total number
of vertex visits, but of the same order of magnitude. As we will show in Section 6,
k can be of order ?(n2).