Lost Hiker Problem

Dennis Shasha

Omniheurist Course

Computer Science


 

Description

A hiker has been hurt somewhere in a k by k mile square. He sends a distress signal having a range of two miles. When your search party is within range of his signal, your directional finder will lead you directly to him, so your task is to GUARANTEE to come within range of that signal as quickly as possible. Assume you can start from any edge of the square and travel continuously and that your Jeep allows you to travel a mile every ten minutes.

Warm-up: For which shape whose area is 100 square miles (10 by 10) could you guarantee to find the hiker in as little as 250 minutes? Solution to warm-up: A rectangle 4 by 25 would do it. You would start from the middle of the 4 side and travel in a straight line to the opposite side. There is a better solution. See if you can find it.

For the puzzle as stated, I know of no 250 minute solution, though Erik and Martin Demaine of MIT found a solution that guarantees to detect the hiker within less than 300 minutes. and here is an even better solution.

Many variants of this puzzle are possible. For example, there may be many search parties or travel may be easier along certain paths. The variants that interest me most, however, have to do with the distress signal. For example, what if the signal is on for a minute and then off for a minute? I don't know whether even a sub-350 minute solution is possible then.

When the distress signal is of constant range and is broadcast continuously, this problem closely resembles the lawnmower problem: you have a square lawnmower and a region. You want to cover the entire region by a shortest-length path

Your Task

I will give you the length of the side of a square. It need not be an integer. Then you will try to find the shortest way to cover the entire square. Your solution will consist of some description of the routes to be used.

Architecture Team

Given a description of the routes, you are to paint the screen with all the area covered and then to verify visually and analytically that the entire square is covered.