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
A robust and fast algorithm for computing exact and approximate shortest visiting routes
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
2004 (English)In: Computational Science and Its Applications - ICCSA 2004 International Conference, Proceedings, Encyclopedia of Global Archaeology/Springer Verlag, 2004, Vol. Part III, 168-177 p.Conference paper, Published paper (Refereed)
Abstract [en]

Given a simple n-sided polygon in the plane with a boundary partitioned into subchains some of which are convex and colored, we consider the following problem: Which is the shortest route (closed path) contained in the polygon that passes through a given point on the boundary and intersects at least one vertex in each of the colored subchains? We present an optimal algorithm that solves this problem in O(n) time. Previously it was known how to solve the problem optimally when each colored subchain contains one vertex only. Moreover, we show that a solution computed by the algorithm is at most a factor times longer than the overall shortest route that intersects the subchains (not just at vertices) if the minimal distance between vertices of different subchains is at least c times the maximal length of an edge of a subchain. Without such a bound its length can be arbitrarily longer. Furthermore, it is known that algorithms for computing such overall shortest routes suffer from numerical problems. Our algorithm is not subject to such problems.

Place, publisher, year, edition, pages
Encyclopedia of Global Archaeology/Springer Verlag, 2004. Vol. Part III, 168-177 p.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 3045
National Category
Computer Sciences
Research subject
Dependable Communication and Computation Systems
Identifiers
URN: urn:nbn:se:ltu:diva-32392DOI: 10.1007/b98053Local ID: 6e46f710-a0de-11db-8975-000ea68e967bISBN: 978-3-540-22057-2 (print)OAI: oai:DiVA.org:ltu-32392DiVA: diva2:1005626
Conference
Computational Science and Its Applications - ICCSA 2004 International Conference : 14/05/2004 - 17/05/2004
Note
Validerad; 2004; 20070110 (ysko)Available from: 2016-09-30 Created: 2016-09-30 Last updated: 2017-10-19Bibliographically approved

Open Access in DiVA

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

Other links

Publisher's full text

Search in DiVA

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

Search outside of DiVA

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

Altmetric score

Total: 11 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