9
$\begingroup$

This is a variant on Polya's orchard problem.1,2 Suppose trees are planted randomly in the plane. The question is: How many trees are visible from the origin as their radii grow?

More precisely, confine attention to the first quadrant, and distribute points uniform-randomly in that quadrant so that each $1 \times 1$ lattice square has a mean density of $d$ points. So, for example, if $d=4$ then a $5 \times 5$ portion of the quadrant should receive $100$ points. (Another model is to insist on $d$ random points per unit lattice square.)

Initially the radii of each tree is $0$ and all are visible from the origin.3 (A tree is visible if at least one point of its bounding circle has a clear line-of-sight to the origin.) As the radii $r$ of the trees grows, fewer and fewer trees are visible from the origin, and eventually some tree engulfs the origin and none are visible.


          VisibileTrees
          $r=0.12$, $19$ (white) disks visible.


The function $V(r)$, the number of trees visible as a function of $r$, decreases from $\infty$ at $r=0$ to eventually $0$. A typical plot of $V(r)$ is shown below (for a different random example).


          OrchardPlot
My first question is:

Q1. What is the expected form of the function $V(r)$? Can some heuristic reasoning suggest its rate of decrease with $r$? Perhaps $V(r) \sim 1/r^2$?

Added (27Jun2019). Here is the above example fit to @fedja's constant: $V(r) = \pi /(4 d r^2)$:


          Fit_s4
And another example (as each run varies quite a bit):
          Fit_s2



Now imagine that you get to choose the planting of the trees, with the stipulation that each unit lattice square must receive $d$ points, and all points are distinct. (Define each lattice square to be open on its bottom and left edges, closed on its top and right edges, so their union covers the quadrant.) The goal is to plant the trees to maximize visibility from the origin as the trees grow. Ideally I'd like $V(r)$ for the ideal arrangement to dominate the visibility functions for all other arrangements of the same number of points. I am not sure there even is such an optimal arrangement.

Q2. What is an arrangement of trees, $d$ per unit lattice square, that maximizes the visibility function $V(r)$?


1 Thomas T. Allen, "Polya's orchard problem." The American Mathematical Monthly 93(2): 98-104 (1986). (Jstor link.)
2 Efficient visibility blockers in Polya's orchard problem.
3 In contrast to lattice points: What fraction of the integer lattice can be seen from the origin?

$\endgroup$
5
  • 3
    $\begingroup$ If the average density is $d$ then the expected number of visible trees in the first quadrant is just $V(r) = d \int_0^\infty \frac{\pi}{2} x \mathbb{P}(\text{tree at distance }x\text{ is visible})\mathrm{d}x$, right? The latter probability is $e^{- d A}$ where $A$ is the excluded area. As $x/r\to\infty$ this area is approximately $A \sim r x$, so that would imply $V(r) \sim \frac{\pi}{2d r^2}$. $\endgroup$ Jun 26, 2019 at 14:24
  • $\begingroup$ @TimothyBudd: Nice! $1/r^2$ is experimentally justified, but with a smaller constant. But these experiments have small $x/r$, so your constant could be the truth. $\endgroup$ Jun 26, 2019 at 14:35
  • 2
    $\begingroup$ My computation gives $\frac{\pi}{4dr^2}$. Does it agree any better with the experiment? $\endgroup$
    – fedja
    Jun 27, 2019 at 3:09
  • $\begingroup$ @fedja: Yes, that does agree better! $\endgroup$ Jun 27, 2019 at 10:00
  • 2
    $\begingroup$ The second question is not very meaningful: you can free up a line, put the trees along it each next one a bit closer to that line than the previous one, and get $V=\infty$. $\endgroup$
    – fedja
    Jun 27, 2019 at 12:22

1 Answer 1

1
$\begingroup$

diagram

When the trees are of radius $r$, a tree at distance $s$ is visible iff there’s at least one sight line from the origin to the tree, at some angle $-{\sin^{-1} \frac sr} \le θ ≤ \sin^{-1} \frac sr$ from center, such that no other tree is centered within the oval of radius $r$ surrounding that sight line. Classify the potential obstructions within these ovals as

  • center field, if they are within all such ovals;
  • left field, if they are within only the ovals with $θ ≤ α$ for some $α$;
  • right field, if they are within only the ovals with $θ ≥ β$ for some $β$.

To first order for small $r$, we can ignore the round ends and approximate these fields as three triangles of area $rs$; we’ll also use the small angle approximation to skip writing $\sin$ and $\sin^{-1}$.

The tree is visible iff: there are no center field obstructions, and the left field obstruction with largest $α$ (if any) and the right field obstruction with smallest $β$ (if any) satisfy $α < β$.

  • The probability that there are no center field obstructions is $e^{-rsd}$.

  • The probability that there are no left field obstructions is $e^{-rsd}$. But if there is one, the largest $α$ has probability density $\frac12 s^2de^{-\frac12(r - sa)sd}\,\mathrm dα$. Given that $α$, the probability that no right field obstructions satisfy $β ≤ α$ is $e^{-\frac12(r + sα)sd}$.

Therefore, the tree is visible with probability

$$e^{-rsd}\left(e^{-rsd} + \int_{-\frac rs}^{\frac rs} \frac12 s^2de^{-\frac12(r - sa)sd} e^{-\frac12(r + sα)sd}\,\mathrm dα\right) = (1 + rsd)e^{-2rsd}.$$

At each distance $s$, we expect $\frac π2 sd\,\mathrm ds$ trees, so the expected number of visible trees should be about

$$\int_0^\infty \frac π2 sd(1 + rsd)e^{-2rsd}\,\mathrm ds = \frac{\pi}{4r^2d}$$

for small $r$. (This agrees with the result suggested without proof in fedja’s comment.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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