𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An approximative solution to the Zookeeper's Problem

✍ Scribed by Håkan Jonsson

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
200 KB
Volume
87
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

Consider a simple polygon P containing disjoint convex polygons each of which shares an edge with P . The Zookeeper's Problem then asks for the shortest route in P that visits all convex polygons without entering their interiors. Existing algorithms that solve this problem run in time super-linear in the size of P and the convex polygons. They also suffer from numerical problems.

In this paper, we shed more light on the problem and present a simple linear time algorithm for computing an approximate solution. The algorithm mainly computes shortest paths and intersections between lines using basic data structures. It does not suffer from numerical problems. We prove that the computed approximation route is at most 6 times longer than the shortest route in the exact solution.

📜 SIMILAR VOLUMES

Approximation algorithms for the watchma
Approximation algorithms for the watchman route and zookeeper's problems
✍ Xuehou Tan 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 261 KB

Given a simple polygon P with n vertices and a starting point s on its boundary, the watchman route problem asks for a shortest route in P through s such that each point in the interior of the polygon can be seen from at least one point along the route. In this paper, we present a simple, linear-tim

An Approximate Solution to the Behrens-F
An Approximate Solution to the Behrens-Fisher Problem
✍ Dinesh S. Bhoj 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 264 KB

An approximate and practical solution is proposed for the Behrens-Fisher problem. This solution is compared to the solutions considered by MEHTA and SRINIVASAN (1970) and WELCH'S (1937) approximate t-test in terms of the stability of the size and magnitude of the power. It is shown that the stabilit

An analytical approximate solution to th
An analytical approximate solution to the problem of precautionary savings
✍ Gabriel Talmain 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 120 KB

This paper considers the problem of precautionary savings for an expected utility specification with finite horizon. The exact solution is known for only a few cases. Numerical methods have limited applications because of Bellman's 'curse of dimensionality'. This paper derives a simple analytical ap