|
iDEA: Drexel E-repository and Archives >
Drexel Theses and Dissertations >
Drexel Theses and Dissertations >
Between a rock and a hard place: Euclidean TSP in the presence of polygonal obstacles
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1860/520
|
| Title: | Between a rock and a hard place: Euclidean TSP in the presence of polygonal obstacles |
| Authors: | Abrahamson, Jeff |
| Keywords: | Computer science
Traveling-salesman problem
Computational complexity |
| Issue Date: | 23-Aug-2005 |
| Abstract: | We present a polynomial-time algorithm for a special case of the Euclidean traveling salesman problem in which a robot must visit all the vertices of two non-intersecting polygons without crossing any polygon edge. If both polygons are convex, one enclosing the other, our algorithm can find the optimal tour of the channel between them in time O(m^3+m^2n) and O(nm+m^2) space, where the exterior polygon has n vertices and the interior m vertices. In the more general case of non-convex polygons (not necessarily nested), the algorithm finds the exact optimum tour in O(n^2m + m^3) time and O(n^2+m^2) space. At the end we give several examples in the context of robot navigation. |
| URI: | http://hdl.handle.net/1860/520 |
| Appears in Collections: | Drexel Theses and Dissertations
|
Items in iDEA are protected by copyright, with all rights reserved, unless otherwise indicated.
|
www.drexel.edu
