#

#
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.