Abstract:
Given two points p and q and a nite number of simple poly-
gons in a plane. The basic version of a touring-a-sequence-of-polygons
problem (in brief: a touring polygons problem, TPP) is how to nd a
shortest path such that it starts at p, then it visits these polygons in the
given order, and nally it ends at q. This paper describes approximate
algorithms for di erent versions of touring polygons problems. Among
its important results it provides, for example, an answer to the previ-
ously open problem \What is the complexity of the touring polygons
problem for pairwise disjoint nonconvex simple polygons?" by providing
a (")-linear approximate algorithm for solving this problem, with
(") = (L0 L1)="
where L0 is the length of the initial path and L is the true (i.e., optimum)
path length. As a further example, this paper nds an approximate so-
lution to the unconstrained touring polygons problem which is known to
be NP-hard.
Description:
You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the original MI_tech website http://www.mi.auckland.ac.nz/index.php?option=com_content&view=article&id=91&Itemid=76 . All other rights are reserved by the author(s).