Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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. , p. 271
Series
Doctoral thesis / Luleå University of Technology 1 jan 1997 → …, ISSN 1402-1544 ; 2000:36
National Category
Computer Sciences
Research subject
Dependable Communication and Computation Systems
Identifiers
URN: urn:nbn:se:ltu:diva-26604Local ID: f2ada1f0-7bc9-11db-8824-000ea68e967bOAI: oai:DiVA.org:ltu-26604DiVA, id: diva2:999770
Note
Godkänd; 2000; 20061116 (haneit)Available from: 2016-09-30 Created: 2016-09-30 Last updated: 2018-01-10Bibliographically approved

Open Access in DiVA

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

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar
Total: 171 downloads
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

urn-nbn

Altmetric score

urn-nbn
Total: 37 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf