From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: Two interesting geometric problems
Date: 29 Jul 1998 07:02:05 GMT

 <ashutosh_1@my-dejanews.com> wrote:
>
>1. You are given an infinite square grid of size L. At the origin of the grid
>stands an observer. At all the other grid points stands a tall tree of radius
>r (r<L)  Find out what is the farthest the observer can see.

I'll take  L = 1. By the way, you probably want  r < (1/2)L.

For each lattice point (a,b) in the first quadrant, compute the interval
of angles blocked by a tree in that position having radius  r.
Actually it's easier to compute the range of the tangents of those angles;
they form an interval whose endpoints are
   -(r*a-b*(a^2+b^2-r^2)^(1/2))/(r*b+a*(a^2+b^2-r^2)^(1/2))
and this expression with  r  replaced by  -r. We need only keep appending
tree at points (a,b) with  0 <= b <= a  until this range of tangents includes
all of  [0,1]; the rest of the 4 quadrants is then also blocked by symmetry.

I did this with some small values of  r. Here are the locations of the last
tree added to block the rest of the view (it's the most distant tree visible,
or tied for it):
	r	tree	distance^2
	1/3,  [2, 1], 	5
	1/5,  [4, 1], 	17
	1/7,  [5, 4], 	41	
	1/10, [9, 4], 	97
	1/15, [14, 5], 	221
	1/20, [19, 6], 	397
	1/25, [19, 16], 617
	1/30, [27, 13], 898
	1/35, [31, 16], 1217
	1/40, [34, 21], 1597
	1/50, [47, 17], 2498
which gives an excellent fit for the hypothesis that the most distant
visible tree is at a distance of about  1/r.

Here's a rough argument as to why this is valid. The tree at point (a,b)
blocks the view through those angles whose tangent is as indicated above.
For small  r  this is very nearly  (b/a) + sqrt(a^2+b^2)/a^2 * r; the
second term is no more than  r/a, so the tangent must be quite close to the
fraction (b/a) in order for the line of sight to be blocked. But
every number in  (0,1) can indeed be well approximated by rationals --
from  continued fractions we expect we can approximate each such number  x
by a fraction b/a with a denominator less than  N  and an error less than  
1/N^2; in particular, with  N  of order  1/r  or so, every number  x  should
be approximated well enough by a fraction with small enough denominator.

[deletia -- djr]
dave