The Watchman Problem is an
optimization
Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...
problem in
computational geometry where the objective is to compute the shortest route a watchman should take to guard an entire area with obstacles given only a map of the area. The challenge is to make sure the watchman peeks behind every corner and to determine the best order in which corners should be visited in. The problem may be solved in
polynomial time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
when the area to be guarded is a
simple polygon
In geometry, a simple polygon is a polygon that does not intersect itself and has no holes. That is, it is a flat shape consisting of straight, non-intersecting line segments or "sides" that are joined pairwise to form a single closed path. If ...
.
[.] The problem is
NP-hard
In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
for polygons with holes,
but may be approximated in polynomial time by a solution whose length is within a polylogarithmic factor of optimal.
[.]
See also
*
Art gallery problem
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 represent ...
, which similarly involves viewing all points of a given area, but with multiple stationary watchmen
References
Geometric algorithms
{{geometry-stub