MINIMUM TRAVEL ROBOT LOCALIZATION

• INSTANCE: A simple polygon P and the visibility polygon V of the location of a robot inside P.

• SOLUTION: A motion scheme for the robot to determine its exact location.

• MEASURE: The distance the robot travels according to the motion scheme.

  
  

• Good News: Approximable within $\vert H\vert-1$ where H is the set of points in P with visibility polygon V [139].

• Comment: 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 $O(\log m)$, where m is the minimum number of edges in an optimal rectilinear tour [374].