We introduce the Observation Route Problem ($\textsf{ ORP}$) defined as follows: Given a set of $n$ pairwise disjoint compact regions in the plane, find a shortest tour (route) such that an observer walking along this tour can see (observe) some point in each region from some point of the tour. The observer does \emph{ not} need to see the entire boundary of an object. The tour is \emph{ not} allowed to intersect the interior of any region (i.e., the regions are obstacles and therefore out of bounds). The problem exhibits similarity to both the Traveling Salesman Problem with Neighborhoods ($\textsf{ TSPN}$) and the External Watchman Route Problem ($\textsf{ EWRP}$). We distinguish two variants: the range of visibility is either limited to a bounding rectangle, or unlimited. We obtain the following results: (I) Given a family of $n$ disjoint convex bodies in the plane, computing a shortest observation route does not admit a $(c\log n)$-approximation unless $\textsf{ P} = \textsf{ NP}$ for an absolute constant $c>0$. (This holds for both limited and unlimited vision.) (II) Given a family of disjoint convex bodies in the plane, computing a shortest external watchman route is $\textsf{ NP}$-hard. (This holds for both limited and unlimited vision; and even for families of axis-aligned squares.) (III) Given a family of $n$ disjoint fat convex polygons, an observation tour whose length is at most $O(\log{ n})$ times the optimal can be computed in polynomial time. (This holds for limited vision.) (IV) For every $n \geq 5$, there exists a convex polygon with $n$ sides and all angles obtuse such that its perimeter is \emph{ not} a shortest external watchman route. This refutes a conjecture by Absar and Whitesides (2006).
Categories: cs.CG