Conference rusure::math

    Does he have a compass or other direction-finding capability?
    (I.e., can he walk a straight line?)
    
    Is the forest convex? (I.e., if points A and B are in the forest, are
    all points of the line AB also in the forest?)
    
      John

    He can walk a straight line.
    
    he does not know if the forest is convex.

Well, it seems to me the best he can do then is walk a straight line in
any arbitray direction.

I say arbitrary, because I'm assuming he can't see light in the "thin"
direction or any other such hints.

So, he walks straight.  In an awful scenario, the forest might be EXTREMELY
long and thin, and he might walk a LONG TIME before hitting a boundary.


Now, the interesting question is whether he should, after walking for
some "long time", make an assumption that it *is* long and thin, and hence
he should make a 90 degree turn.

How long should he wait to make such a decision ?  I suppose it has to
do with the expected probability distribution of shapes.

Let's try real numbers.  Suppose I know the forest is 100 square miles.
I'm the jumper.

I walk for about 15 miles.  If it were square, and I jumped into the middle,
I'd expect to walk about 5 miles (or a bit more if I'm walking on a diagonal).

But I've walked 15, so I know I'm in some sort of elongated shape.  So
I might as well take a 90o turn.

But it is an interesting turn as to *when* to make such a turn.

Now that I've thought out loud for a few minutes, I'm a bit more intrigued,
thank you.

/Eric

    Given the forest may not be convex then whatever path he walks you
    could say "yes, but that's still in the forest".
    
    How about this: is there a distance d such that the hiker can always
    see the edge of the forest if he comes within d units of the edge?
    
    Suppose the forest were in the shape of an annulus, i.e., a circle
    of "non-forest", surrounded by a larger circle. The area between the
    circles -- and nothing else -- is the forest. This is possible, right?
    
      John

Gee, I sure wish we could draw pictures.

John, I don't quite get your concerns yet.


To me, a nonconvex forest might be one in the shape of a circle drawn
with the side edge of a piece of chalk.


So, we have a circle of nonforest in the middle.  Then we have a ring
which is the forest.  Then we have nonforest forever outside that.

This is my idea of an annulus forest.  But I don't see any "problem"
with this kind of forest.  

/Eric

	Suppose, in the worst case , the forrest is extremely narrow,
	he lands close to one end, but by bad chance he choses to walk
	along the entire length of the forrest.

	If the area of the forrest is A and the cicumference is L,
	then the isoperimetric inequality says that

		L^2 >= 4piA

	with equality only for a circel.

	In this cas he would have to walk no more than 

		L/2 = 0.5*sqrt(4piA) 

.0>    A Paratrooper lands in a forest of unknown shape but known area.
>    What would be his minimal path out of the forest ?

I'm not sure what minimal means here.  

The usual meaning would be, what is the shortest possible path for a random
jumper in a random forest.  The answer is "arbitrarily small", since the jumper
might walk in the direction of the nearest edge, and might land arbitrarily
close to that edge.

Minimal from the jumper's point of view might be different.  Given a walking
strategy (as in .3), there is a distance to the outside for any given forest.
We could define a worst case distance for a given strategy.  Then we could call
the minimal path the path given by the strategy which gives the lowest worst
case distance.  This is a minimax definition.

But as John says

.4>    Given the forest may not be convex then whatever path he walks you
>    could say "yes, but that's still in the forest".

For any strategy, there exists a forest in which the distance is unbounded.  So
the minimax definition gives an unbounded answer.

.4>    How about this: is there a distance d such that the hiker can always
>    see the edge of the forest if he comes within d units of the edge?

Right.  If we add this then the problem gets more interesting.

>    Suppose the forest were in the shape of an annulus, i.e., a circle
>    of "non-forest", surrounded by a larger circle. The area between the
>    circles -- and nothing else -- is the forest. This is possible, right?

I think if we eliminate holes in the forest we may be able to bound the worst
case path.  Is this what topologists mean by simply connected?

    
.5> So, we have a circle of nonforest in the middle.  Then we have a ring
> which is the forest.  Then we have nonforest forever outside that.
> This is my idea of an annulus forest.  But I don't see any "problem"
> with this kind of forest.  
    
    Yes, lacking decent graphics it sounds (reads?) like what I had in mind.
    Suppose the hiker walks out of the forest into the inner "clearing".
    Is that a success? He's "out of" the forest but not "outside of" the
    forest. Just trying to be Semantically Correct, and avoid various
    degenerate solutions involving space-filling curves with finite area.
    
    If you have a lower bound on the width of the forest ("2d") because you
    can see the edge at distance < d, then you have an upper limit on 
    how far you have to walk in a straight line. Which then looks to be
    the best strategy. For if you walk a while then turn 90 degrees, 
    if you turn at JUST the wrong moment you'll be walking an extra d units.
    More if you turn more than 90 degrees.
    
      John

1. MOANING ABOUT PROBLEM DEFINITION

>    he does not know if the forest is convex.

	Are you *sure* about this? I agree with other folk that whatever 
finite path the paratrooper chooses, you could imagine a forest that 
encloses the path. I don't think the intent of the puzzle is to have a
visibility radius or a probabilistic interpretation of the word minimal. As the 
problem is stated, it is confusing, and people are getting bogged down in 
trying to define it more clearly.

2. CONVEX FOREST

	Anyway, suppose that we do know that the forest is convex, and has
area A. The paratrooper is trying to specify a path of shortest length that
will guarantee that he exits from the forest at some point.

	For instance, if the paratrooper walks in a circle of radius >
sqrt(A/pi) then he must exit the forest. So we know that the minimal length
of the path =< 2*sqrt(pi*A).

	If we return to our starting point then the circular path minimizes the
length for a given area enclosed. But we are not required to come back to the 
starting point. If we walk a semi-circular arc of radius > sqrt(2*A/pi) then by 
convexity we enclose an area > A, and so at some point in the walk of length 
> sqrt(2*pi*A) we exit the forest.

	I think a semi-circle is optimal, by an argument which involves
reflecting the forest in an axis through the the start & end points of the
walk.

3. SIMPLY-CONNECTED FOREST

	If all we know is that the forest is simply-connected, on the other
hand (i.e. all in one lump & no holes) then what can we say? Any stretch of
walk which does not return to our starting point is a waste of time, since it
might be coated with an infinitely thin layer of trees. The only way we can
get out of the forest is by traveling in a loop! Because anything contained in
a loop is guaranteed to be forest. The length of walk is maximal for a given
area if we just travel in one loop, and that loop is circular, so we get the
answer 2*sqrt(pi*A).

	I think a circle is a boring answer to the problem, and so I prefer
the convex forest to the simply-connected forest, and I return to my suggestion
that convexity is the original notion of the puzzle's inventor.

Andrew.

Yes, to me if forest is an annulus, and hiker walks into the central clearing,
I'd say he's "out".

To make it more real, let's say he's got a mirror, with which he can catch
the search pilot's attention if he can get out of the shade.  Hence any
clearing is good enough.


However, I agree with the sentiments of other readers that without further
restrictions on the shape of our forest, it's conceivable that any chosen
path might murphyiously be coincident with the shape of a strange forest.

/Eric

	Let's imagine the distance to the closest point to get out of the
	forest is : r
	Now let's draw a circle of center=Paratrooper's position,radius=r.
	The surface of this circle is pi*r2 and it is smaller than A for
	sure. So we have A >= pi*r2 and therefore r <= sqrt(A/pi).
    	
	Gerard
    

    So to reply to .0,if the guy just walks in a straight line for longer
    than sqrt(A/pi) he is ensured to be out of the forest.May not be
    minimal but safe !

.11 gives the upper bound to the closest point outside the forest, for a convex
forest.  This would help a jumper with a good map and LORAN.

.12 uses it as an upper bound to the most distant part of the forest.  As John
and others have pointed out, even for a convex forest, the most distant point
could be arbitrarily far away.

I think .9 gives the right answers for convex and simply connected forests.

    
    RE-1:
    I don't thinkit matters if the forest is convex or not,and whatever 
    shape it is.
    Let's say the paratrooper is in point O and to the distance r from the
    closest point ,and R of the most distant point on the boundary and draw
    2 circles of center o and radius r and R.
    You will always have this :
    	pi*r2 < A < pi*R2
    So in the best case, if the guy picks up the right direction ,he will
    walk only r and r will be at the maximum,equal to sqrt(A/pi)
    If he picks up the worst case direction,he will have to walk R,and 
    R will have to be at least sqrt(A/pi).So if he walks at least this
    distance on a straight line ,he will be out of the forest for sure
    whatever the direction he takes .
    
    I agree this may not be the most effective solution but it seems to
    work even if you have holes in the forest,or a forest which is very
    long and very thin. 
    
    Gerard 
    	

>    Let's say the paratrooper is in point O and to the distance r from the
>    closest point ,and R of the most distant point on the boundary and draw
    
    Except that R can be infinity if the forest is allowed to be
    arbitrarily thin. Picking the "wrong" direction might result
    in death by starvation. Or boredom.
    
      John

    My apologies.
    I posted this just before the weekend.Different time zones and 
    weekends(we don't work on fridays)kept me from seeing all the
    replies.I certainly didn't expect so many.
    Anyway... i thought about it while crawling in a cave yesterday.
    I do think the forest is meant to be convex.
    I don't think the hiker should try to theorize about the probable
    shape because there are infinite possibilities(not only for 
    the shape but also for his position in the forest).
    
    I have an idea but no actual proof.
    If i'm right a circle has the least circumference for a given area
    (less than any polygon).
    In my opinion he should walk the radius and then the circumference
    of a circle with the same area as the forest.
    
    Is this correct ?
    
    If it is,would it be different if the forest is nonconvex ?
    
    

    Several more remarks:
    I don't think you should assume gradual thinning of the forest
    so he can see out.He knows he's out only when he gets there.
    There are no circles of nonforest within the forest
    "out of the forest" means beyond the outer limits.

The reason a nonconvex forest has a different answer is that whatever
path you suggest the hiker take, one can imagine a very thin but long
forest that just *happens* to *exactly* match the path he takes !  (improbably
but possible, right ?)

/Eric