About: Watchman route problem

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. The problem may be solved in polynomial time when the area to be guarded is a simple polygon. The problem is NP-hard for polygons with holes, but may be approximated in polynomial time by a solution whose length is within a polylogarithmic factor of optimal.