Up: Games and Puzzles
Previous: MINIMUM GRAPH MOTION PLANNING
A simple polygon P and the visibility polygon V of the location of a
robot inside P.
A motion scheme for the robot to determine its exact location.
The distance the robot travels according to the motion scheme.
- Good News:
where H is the set of points in P with
visibility polygon V .
The problem SHORTEST WATCHMAN ROUTE where the polygon P have
holes and the problem is to find a shortest tour inside P such that the robot
can see all of P is approximable within ,
where m is the
minimum number of edges in an optimal rectilinear tour .