Files and links (1)
PDFOpen Access (License Unspecified), Open Access
Thesis
Between a rock and a hard place: Euclidean TSP in the presence of polygonal obstacles
Master of Science (M.S.), Drexel University
May 2005
DOI:
https://doi.org/10.17918/etd-520
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.
Metrics
23 File views/ downloads
17 Record Views
Details
- Title
- Between a rock and a hard place
- Creators
- Jeff Abrahamson - DU
- Contributors
- Ali Shokoufandeh (Advisor) - Drexel University (1970-)
- Awarding Institution
- Drexel University
- Degree Awarded
- Master of Science (M.S.)
- Publisher
- Drexel University; Philadelphia, Pennsylvania
- Resource Type
- Thesis
- Language
- English
- Academic Unit
- College of Arts and Sciences; Drexel University; Mathematics
- Other Identifier
- 520; 991014632577204721