Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Polya's orchard problem asks for which radius $\rho$ of trees at each lattice point within a distance $R$ of the origin block all lines of sight to the exterior of the orchard.
         orchard
It has been established that rays to infinity are completely blocked iff $\rho \ge 1/\sqrt{R^2 + 1}$, when $R$ is an integer. (T.T. Allen, "Polya's orchard problem," The American Mathematical Monthly 93(2): 98-104 (1986).) The above shows a quarter of an orchard with $R=6$, $\rho=1/\sqrt{37}=0.164$, and some random rays.

I am wondering if disks are the most efficient blockers in terms of area. More precisely:

For a given $R$, is there a centrally symmetric convex body $K$ of area less than $\pi \rho^2$ which when translated to all lattice points within distance $R$ of the origin, block all rays from the origin to the outside?

My guess is that the answer is Yes, in which case it would be interesting to know the shape of the area-optimal blockers. In particular, are they polygons? The same question may be posed in $\mathbb{R}^d$: are they polytopes?

Edit. Here is the chord construction for $R=2$ from the first paragraph of Douglas's construction, as I understand it:
DZ constr

share|improve this question
    
I think that what you have is almost what the construction would give for those $12$ disks of radius $1/\sqrt{5}.$ By my calculations the outer (shorter) vertical and horizontal segments exactly meet the ones of slope $\pm 1.$ The inner (longer) horizontal and vertical lines for the circles with center at distance $2$ can be discarded, those circles don't block anything not already blocked. I put a picture below of what I think one gets. –  Aaron Meyerowitz Apr 26 '11 at 7:35
    
improvement This problem is kind of subtle. One could do this same cord construction allowing disks of different sizes at different points. Furthermore, the horizontal and vertical cords of length $\frac45$ can be replaced by segments of length $1$ going through the center of each circle. These are longer but also more central and the area turns out to be smaller. I added a picture of this to my answer below. –  Aaron Meyerowitz Apr 28 '11 at 4:01
    
more improvement And even that is not optimal. I think that squares of side $\frac23$ are. I added yet another picture. –  Aaron Meyerowitz Apr 28 '11 at 10:01

3 Answers 3

There are finitely many lattice points within $R$ of the origin. For each lattice point $v$ other than the origin, there are two rays through the origin tangent to the circle of radius $\rho$ about $v$. Associate the chord connecting the two points of tangency to $v$. This chord blocks the same rays through the origin as the circle of radius $\rho$ about $v$. The convex hull of the translates of these chords to the circle about the origin is a polygon inscribed in the circle of radius $\rho$. This polygon has strictly lower area than the circle, and copies centered at the lattice points block all rays from the origin.

The areas of centrally symmetric convex bodies whose translates block all rays from the origin do not have a positive lower bound if you allow them to intersect. You can thicken a line segment from $(-2,-2)$ to $(2,2)$ so that the translate to $(1,1)$ still contains the origin. This might be viewed as trivial, and some restriction might be nontrivial. Requiring the translates not to contain the origin still doesn't give a positive minimum area (for $R \gt \sqrt2$) by changing the above example to a rectangular thickened line segment from $(-1+\epsilon,-1+\epsilon)$ to $(1-\epsilon,1-\epsilon)$ with a width greater than $2\epsilon$.

share|improve this answer
    
Beautifully clear argument, Douglas---Thanks! –  Joseph O'Rourke Apr 25 '11 at 14:55
    
So maybe we should for minimal width of a blocker and subject to that inclusion minimal. Of courselves maybe we just saw it. –  Aaron Meyerowitz Apr 26 '11 at 0:30
    
OR require the 8 symmetries of a square (that might amount to the same thing) –  Aaron Meyerowitz Apr 26 '11 at 7:39
1  
Note that the construction does not produce polytopes for $d \ge 3$. E.g., in $\mathbb{R}^3$, convex hulls of disks. –  Joseph O'Rourke Apr 26 '11 at 9:41
1  
I'm not sure about $\mathbb{R}^3.$ For $R=1$ in $\mathbb{R}^2$ we have $4$ tangent but internally disjoint disks of radius $1/\sqrt{2}$ and these get slimmed down to $4$ squares of side $1.$ For $R=1$ in $\mathbb{R}^3$ we have $6$ spheres of radius $\sqrt{2}/\sqrt{3}$ which are not internally disjoint. It seems reasonable that we would slim these down to cubes of side $1.$ I'll take a wild leap and predict cubo-octahedra (maybe regular but probably not not) if we go out to the next $12$ lattice points such as $(\pm1,0,\pm1)$ –  Aaron Meyerowitz Apr 26 '11 at 13:50

Here is what I think Douglas's construction (slightly modified) gives for $R=2$ There is no need to actually us the circles at $R=2$ since they are themselves blocked by the circles at $R=1$. These semi-regular octogons are inscribed in disks of radius $1/\sqrt{5}$. The indicated ray has slope $1/2.$

alt text

improvement These octagons have area $\frac{14}{25}=0.56$ They can be replaced by tilted squares of side $\sqrt{\frac12}$ and area $\frac{1}{2}$ and they (obviously) still block.

alt text

More improvement But actually squares of side $\frac23$ with area $\frac49$ are even better! I think that must be the minimum area for a blocker (out to $R=\sqrt{2}$) with the 4 lines of reflective symmetry. alt text

share|improve this answer
    
Yes, nice improvement, Aaron! –  Joseph O'Rourke Apr 26 '11 at 9:39
    
Beautiful, Aaron! I agree these 2/3's squares are likely the opimal blockers (for small $R$). –  Joseph O'Rourke Apr 28 '11 at 11:56
1  
And I'm sure the lumber companies would love to have square trees like this! –  Joel David Hamkins Apr 28 '11 at 13:56

Polya's result can't be improved asymptotically. If we take $\rho\sim\frac cR$ with $c<1$ then positive ratio of rays will not be blocked (as $R\to \infty$). This ratio as a function of $c$ can be calculated explicitly, see for example The Statistics of Particle Trajectories in the Homogeneous Sinai Problem for a Two-Dimensional Lattice. The lattice $\mathbb{Z}^2$ asymptotically isotropic: this ratio does not depend on angles. In partiqular it means that circles asymptotically are best possible blockers: if in some direction the blocker has smaller width (at least from one side from the center; in this direction from one side the blocker looks like a circle of radius $\rho=cR$ with $c<1$) then the ratio of unblocked rays in this direction will be bigger.

For a fixed $R$ best possible blocker can be founf explicitly. As in original proof we can take all integer points inside given circle and consider all rays passing through this points. If two adjacent rays pass through $A_1=(x_1,y_1)$ and $A_2=(x_2,y_2)$ then blockers at this points must block the ray through $A_3=(x_1+x_2,y_1+y_2)$ (which is outside given circle). Bases of the altitudes from $A_1$ and $A_2$ on $OA_3$ must belong to blockers. It means that optimal blocker is convex hull of all such bases.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.