# Applying analysis to solve a line-of-sight problem

This was an optional h.w. problem:

You are at the origin in $\mathbb{Z}\times\mathbb{Z}$. There are trees of a fixed finite radius at each point in $\mathbb{Z}\times\mathbb{Z}$ (other than the origin).

How far can you see?

This was asked in (I think), the context of the Stone-Weierstrass Theorem. So I have been thinking there must be some distance where the diameters of the trees visually converge and you get a polynomial approximation of a visual boundary.

-

I don't know the exact answer, but I can derive a hopefully reasonable upper bound.

Consider a line of sight in the direction $\alpha$. By the symmetries (dihedral group of order 8) we can assume that $0\le\alpha\le\pi/4$. Let $\rho=\tan\alpha$ be the slope of this line, so we are looking along the line $L:y=\rho x$.

Pick an integer $N$ such that $N-1>1/r$. The line $L$ intersects the vertical lines $x=i$, $i=1,2,\ldots,N$ at points $P_i=(i,i\rho)$. [Edit: A silly but potentially confusing typo was here as I had written $N\rho$ in place of $i\rho$ ] Let us consider the fractional parts of the $y$-coordinates of these points. For the point $P_i$ this is $y_i=\{i\rho\}=i\rho-[i\rho]$. The numbers $y_1,y_2,\ldots,y_N\in [0,1)$. Let's put these $N$ numbers into $N-1$ buckets according to the value of $[(N-1)y_i]\in\{0,1,\ldots,N-2\}$. By the pigeon hole principle at least two number, say $y_k$ and $y_\ell$ end up in the same bucket. Without loss of generality we can assume that $k>\ell$. Then $|y_k-y_\ell|\le1/(N-1)<r$. But we also have $$y_k-y_\ell\equiv y_{k-\ell} \pmod1.$$ (or $y_k-y_\ell$ differs from $y_{k-\ell}$ by an integer). Therefore the point $P_{k-\ell}$ is within distance $r$ of a point of $\mathbf{Z}\times\mathbf{Z}$. Obviously here $0<k-\ell\le N$.

We have shown that this line will get blocked at a distance at most $N\sqrt{1+\tan^2\alpha}\le \sqrt2 N$. Here $N=1+\lceil(1/r)\rceil$, so we have shown that the maximum distance $d=d(r)$ that we can see satisfies the inequality $$d(r)\le\sqrt2\left(1+\lceil\frac1r\rceil\right).$$

-
A good bound for $d(r)$! –  André Nicolas Jul 8 '11 at 22:53
@user6312: Dunno :-) I just saw that the first lemma of Diophantine appoximation can be used here to get a bound that probably is correct up to a constant multiplier. I should have guessed that this is a known problem. Thanks for the links. –  Jyrki Lahtonen Jul 9 '11 at 5:42
I have been remiss in not properly thanking you. Please also accept my apologies. Best, Andrew –  Andrew Sep 15 '11 at 21:38

This the famous Polya Orchard Problem.

The link is to a thorough discussion by Honsberger, marred a little by the fact that it comes from Google Books. The discussion is quite elementary.

Another detailed discussion can be found here. Somewhat more machinery is used.

I do not know of a connection with the Stone-Weierstrass Theorem, but that could very well be due to my weaknesses in analysis.

-
Thanks. I am only a self-studier (sorry to hide behind that). In taking a look at those sources, it seems the orchard has a given radius rather than being the entire ZxZ. Does that make a difference? –  Andrew Jul 8 '11 at 20:42
No difference. Typically, a relationship is found between radius $r$ of trees and maximum radius $R$ of an orchard such that you can see some part of its boundary from the origin. You will note that Lahtonen gave a quick nice argument that says roughly $Rr <\sqrt{2}$. The references I gave basically improve the $\sqrt{2}$ to $1$, and I think one cannot do better. You can google Polya Orchard Problem for other papers. So to repeat, $R$ is basically max. line of sight distance. –  André Nicolas Jul 8 '11 at 22:07
Thanks again. People are so generous here. –  Andrew Jul 8 '11 at 22:32