Journal article
Euclidean TSP on two polygons
Theoretical computer science, v 411(7-9), pp 1104-1114
28 Feb 2010
Featured in Collection : UN Sustainable Development Goals @ Drexel
Abstract
We give an O(n(2)m+nm(2) + m(2) log m) time and O(n(2) + m(2)) space algorithm for finding the shortest traveling salesman tour through the vertices of two simple polygonal obstacles in the Euclidean plane, where n and m are the number of vertices of the two polygons. By obstacle, we mean that the tour may not cross between the interior and exterior of either polygon. We also consider the problem's extension to higher dimensions, proving that, if P not equal NP, constructing a shortest TSP tour on the vertices of two non-intersecting polytopes is NP-hard if the polytopes are similarly viewed as obstacles. (C) 2009 Elsevier B.V. All rights reserved.
Metrics
Details
- Title
- Euclidean TSP on two polygons
- Creators
- Jeff Abrahamson - Drexel UniversityAli Shokoufandeh - Drexel University
- Publication Details
- Theoretical computer science, v 411(7-9), pp 1104-1114
- Publisher
- Elsevier
- Number of pages
- 11
- Grant note
- ONR-N000140410363 / Office of Naval Research
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Computer Science
- Web of Science ID
- WOS:000274886700015
- Scopus ID
- 2-s2.0-75049083380
- Other Identifier
- 991019168500504721
UN Sustainable Development Goals (SDGs)
This publication has contributed to the advancement of the following goals:
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Web of Science research areas
- Computer Science, Theory & Methods