Watchman route problem
Encyclopedia
The Watchman Problem is an optimization
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. There are polynomial-time solutions but they all suffer from severe numerical problems inherent in the computations.
Note that this is not the same as the museum problem, which is about a similar situation, but with multiple, stationary watchmen.
Optimization (mathematics)
In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....
problem in computational geometry
Computational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...
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. There are polynomial-time solutions but they all suffer from severe numerical problems inherent in the computations.
Note that this is not the same as the museum problem, which is about a similar situation, but with multiple, stationary watchmen.