Approximation algorithms for geometric tour and network design problems (extended abstract)
Cristian S. Mata, Joseph S. B. Mitchell · 1995
RouteProblem:Let P be a polygonal room, possibly with "holes" (obstacles), having n vertices.The problem of computing a shortest tour in order that a mobile guard can "see" all of T is known as the Watchman Route Problem (WRP).If P is a simple polygon (having no holes), then WRP can be solved exactly, in time 0(n4) [7, 23].However, WRP is known to be NP-hard if ~has holes (a simple reduction from Euclidean TSP; see [8]), even if T is rectilinear.But, as with RBSP, no approximation algorithms have previously been found for this problem.We give an O(log m) approximation algorithm for the WRP when the polygon T is rectilinear, where m < n is the minimum number of edges in a shortest rectilinear watchman route.