Digitala Vetenskapliga Arkivet

Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
A robust and fast algorithm for computing exact and approximate shortest visiting routes
Luleå tekniska universitet, Institutionen för system- och rymdteknik, Datavetenskap.
2004 (Engelska)Ingår i: Computational Science and Its Applications - ICCSA 2004 International Conference, Proceedings: International Conference, Assisi, Italy, May 14-17, 2004, Proceedings, Part III / [ed] Antonio Laganá, Marina L. Gavrilova, Vipin Kumar, Youngsong Mun, C. J. Kenneth Tan, Osvaldo Gervasi, Encyclopedia of Global Archaeology/Springer Verlag, 2004, Vol. Part III, s. 168-177Konferensbidrag, Publicerat paper (Refereegranskat)
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.

Ort, förlag, år, upplaga, sidor
Encyclopedia of Global Archaeology/Springer Verlag, 2004. Vol. Part III, s. 168-177
Serie
Lecture Notes in Computer Science, ISSN 0302-9743 ; 3045
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
Kommunikations- och beräkningssystem
Identifikatorer
URN: urn:nbn:se:ltu:diva-32392DOI: 10.1007/978-3-540-24767-8_18Scopus ID: 2-s2.0-35048813099Lokalt ID: 6e46f710-a0de-11db-8975-000ea68e967bISBN: 978-3-540-22057-2 (tryckt)ISBN: 978-3-540-24767-8 (digital)OAI: oai:DiVA.org:ltu-32392DiVA, id: diva2:1005626
Konferens
Computational Science and Its Applications - ICCSA 2004 International Conference : 14/05/2004 - 17/05/2004
Anmärkning

Validerad; 2004; 20070110 (ysko)

Tillgänglig från: 2016-09-30 Skapad: 2016-09-30 Senast uppdaterad: 2023-11-09Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopus

Sök vidare i DiVA

Av författaren/redaktören
Jonsson, Håkan
Av organisationen
Datavetenskap
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetricpoäng

doi
isbn
urn-nbn
Totalt: 325 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf