Change search
ReferencesLink to record
Permanent link

Direct link
The Euclidean traveling salesman problem with neighborhoods and a connecting fence
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
2000 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

An important class of problems in robotics deals with the planning of paths. In this thesis, we study this class of problems from an algorithmic point of view by considering cases where we have complete knowledge of the environment and each solution must ensure that a point-sized robot capable of moving continuously and turning arbitrarily accomplishes the following: (1) visits a given set of objects attached to an impenetrable simple polygon in the plane, and (2) travels along a path of minimum length over all the possible paths that visit the objects without crossing the polygon. In its general form, this is The (Euclidean) Traveling Salesman Problem with Neighborhoods and a Connecting Fence. We make several contributions. One is an algorithm that computes a shortest watchman path in a rectilinear polygon in time polynomial in the size of the polygon. Each point in the polygon is visible from some point along the computed path, which is a shortest visiting path for a set of convex polygons, each of which is bounded by a chord in the interior of the polygon. For the special case of computing a shortest watchman route, where the end points of the resulting path must coincide, we give a polynomial-time algorithm for general simple polygons. We also give substantially faster and more practical algorithms for computing provably short approximations, that is watchman paths/routes with lengths guaranteed to be at most a constant times longer than the length of a shortest watchman path/route only. To achieve one of these approximations, we develop a linear-time algorithm for computing a constant factor approximation in the case where the convex polygons are impenetrable. For this problem, which is called the Zookeeper's Problem, we show how an exact solution can be computed in linear time when the number of convex polygons is constant. We also present an application of our results to the computation of both exact and approximate solutions to the problem of computing a shortest visiting route for a set of lines in the plane.

Place, publisher, year, edition, pages
Luleå: Luleå tekniska universitet, 2000. , 271 p.
Doctoral thesis / Luleå University of Technology 1 jan 1997 → …, ISSN 1402-1544 ; 2000:36
Research subject
Dependable Communication and Computation Systems
URN: urn:nbn:se:ltu:diva-26604Local ID: f2ada1f0-7bc9-11db-8824-000ea68e967bOAI: diva2:999770
Godkänd; 2000; 20061116 (haneit)Available from: 2016-09-30 Created: 2016-09-30Bibliographically approved

Open Access in DiVA

fulltext(100190 kB)0 downloads
File information
File name FULLTEXT01.pdfFile size 100190 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Jonsson, Håkan
By organisation
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

ReferencesLink to record
Permanent link

Direct link