Change search
ReferencesLink to record
Permanent link

Direct link
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. , 22 p.
Research report / Luleå University of Technology, ISSN 1402-1528 ; 2004:10
Research subject
Dependable Communication and Computation Systems; Industrial Electronics
URN: urn:nbn:se:ltu:diva-24344Local ID: a94c7df0-ece5-11db-bc0c-000ea68e967bOAI: diva2:997396
Godkänd; 2004; 20070417 (ysko)Available from: 2016-09-29 Created: 2016-09-29Bibliographically approved

Open Access in DiVA

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

Search in DiVA

By author/editor
Jonsson, HåkanSundberg, Sofia
By organisation
Computer ScienceEmbedded Internet Systems Lab

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