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
On the problem of computing zookeeper routes
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Embedded Internet Systems Lab.
2004 (English)Report (Other academic)
Abstract [en]

The Zookeeper's Problem is a shortest-path problem that, given a simple polygon (a zoo) containing a set of disjoint convex polygons (cages) attached to the boundary of the zoo, asks for a shortest route (closed path) in the zoo that intersects the boundaries of all cages without entering their interiors. The literature contains several algorithms for variants of this problem some of which compute exact and some approximate solutions. However, no implementations have been reported. Moreover, concerns have also been raised about the numerical properties of the algorithms that compute exact solutions. In this paper we present a study of two algorithms for the Zookeeper's Problem. One of them compute exact solutions and the other provably good approximations. We give observations about the algorithms and the solutions they compute. We also present an experimental study based on an implementation of the algorithms in Java.

Place, publisher, year, edition, pages
Luleå: Luleå tekniska universitet, 2004. , p. 22
Series
Research report / Luleå University of Technology, ISSN 1402-1528 ; 2004:10
National Category
Computer Sciences Other Electrical Engineering, Electronic Engineering, Information Engineering
Research subject
Dependable Communication and Computation Systems; Industrial Electronics
Identifiers
URN: urn:nbn:se:ltu:diva-24344Local ID: a94c7df0-ece5-11db-bc0c-000ea68e967bOAI: oai:DiVA.org:ltu-24344DiVA, id: diva2:997396
Note
Godkänd; 2004; 20070417 (ysko)Available from: 2016-09-29 Created: 2016-09-29 Last updated: 2018-01-10Bibliographically approved

Open Access in DiVA

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

Search in DiVA

By author/editor
Jonsson, HåkanSundberg, Sofia
By organisation
Computer ScienceEmbedded Internet Systems Lab
Computer SciencesOther Electrical Engineering, Electronic Engineering, Information Engineering

Search outside of DiVA

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