d

ar
Aw
On Higher Dimensional Orchard Visibility Problem

ce
en
Shengning Zhang

ci
lS
Abstract. In this article, we study Pólya’s orchard visibility prob-
lem in arbitrary dimension d: suppose at every integral point in Rd ,

oo
centered a small d-dimensional ball with radius r (which is considered
as a tree at the integral point), given a d-dimensional ball centered
at the origin O with radius R (which is considered as the orchard),
h
it asks for the smallest r such that every ray starting from O will hit
some tree in the orchard. We give both upper and lower bounds of
Sc

the minimal value of r, say ρ in terms of R, moreover, we prove that

1
as R → ∞, ρ = O(R− d−1 ).
h

1. Introduction
ig

Let Λ be the set of lattice points Zd \O in Rd , where O is the origin. Let

B(O, R) be the closed ball in Rd centered at O with radius R > 1. Centering
H

at every integral point P ∈ B(O, R), is a small closed ball B(P, r) with given
small radius r > 0. The original Pólya’s orchard visibility problem considers
au

the case d = 2, when the disc B(O, R) is thought as a round orchard and every
B(P, r) a tree at P , it asks for the smallest r, which we denote by ρ, so that
one standing at the center O cannot see through the orchard, that is, for any
.Y

ray l starting from O, l ∩ B(P, r) 6= ∅ for some P .

In [1], it proved that

-T

1 1
(1.1) √ <ρ< .
R2 +1 R
S.

Indeed, in an earlier paper [2], Thomas Tracy Allen had proved that
1
(1.2) ρ= .
21

In this paper, we’d like to study the general Pólya’s orchard problem in arbi-
20

trary dimension d and prove similar bounds as in (1.1). Our strategy follows
[3], where, however, only deals with the 2 and 3 dimensional cases.
 d
2 Leo

ar
2. Lower bounds

Aw
Consider in Rd the d-dimensional cuboid C with diagonal vertices O and D :=
(1, 1, · · · , 1, [R] + 1), where [R] is the floor function of R. Then
C ∩ Zd = {(x1 , · · · , xd ) ∈ Zd | xi ∈ [0, 1], ∀i = 1, · · · , d − 1; xd ∈ [0, [R] + 1]}.

ce
Apparently,
p D is not in B(O, R). The segment OD is of the length
(d − 1) + R2 , and any P ∈ C ∩ Zd has the distance squared dist(P, OD)2
to OD

en
(d − 1 + ([R] + 1)2 )(x21 + · · · + x2d ) − (x1 + · · · + xd−1 + ([R] + 1)xd )2
(2.1)
d − 1 + ([R] + 1)2

ci
This lead us to our first result, which is a direct generalization to the first
inequality of (1.1).

lS
Proposition 1. notations as above
√
(2.2) p
d−1
d − 1 + ([R] + 1)2
h < ρ.
oo
Proof: Consider the formula (2.1), apparently that among all integral
points in C other than O and D, P0 = {0, · · · , 0, 1} minimize the expression,
Sc

when
d−1
dist(P0 , OD)2 = .
d − 1 + ([R] + 1)2
h

(see the figure below)

ig
H
au
.Y
-T
S.

Figure 1
√
d−1
So if the tree radius r can block the orchard, it must bigger than √ .
21

d−1+([R]+1)2
This completes the proof. 
20

The proposition tells us that ρ grows faster than the rate of R−1 as R goes to
infinity, however, it is not the exact rate of growth of ρ, so we want a better
 d
Orchard Visibility Problem 3

ar
lower bound of ρ in terms of R. Indeed, the proof of the proposition tells

Aw
us that, to obtain such a lower bound, we have to consider a “finer” solid
containing the ray than the coboid C above. To use such a solid in higher
dimension, we have to use the volume formula of a lattice polyhedron in higher
dimension developed by Macdonald in [4], which is the generalization of Pick’s

ce
Theorem used in [3, Theorem 2.2]. Now we summarize below.

Let Zd ⊂ Rd be the standard integral lattice, X a d-dimensional polyhedra in

en
Rd whose vertices are all in Zd . Let ∂X be the boundary of X, which can be
viewed as a d − 1- simplicial complex. For any integer n > 0, write
1

ci
L(n, X) = |X ∩ Zd |,
n

lS
and
1
M (n, X) = L(n, X) − L(n, ∂X),
2
then, we have the volume of X can be computed by:

 
h oo
Proposition 2 (Macdonald’s Theorem). The volume of the polyhedra V ol(X)
equals
 
d−1 d−1
Sc
2
(d−1)d! {M (d − 1, X) − M (d − 2, X) + M (d − 3, X)
1 2
− · · · + (−1)d−1 M (0, X)},
h

where M (0, X) = 1 if d is even, M (0, X) = 0 if d is odd.

ig

Now we give us first theorem

Theorem 1. There is a constant c > 0 such that
H

(2.3) ([R] + 1)ρd−1 > c.

au

Remark 1. The constant c is given by the volume of a polyhedra, which can be

computed using Macdonald’s Theorem above. The key is to construct a proper
.Y

polyhedra, which will be clear in the proof of the theorem.

-T

Lemma 1. Point Q ∈ Zd ∩B(O, R), if for any P ∈ Zd ∩B(O, R), OB∩B(P, r) =

∅, then the coordinates of Q are coprime, that is, if Q = (a1 , · · · , ad ) then
S.

gcd(a1 , · · · , ad ) = 1.
The lemma comes from an easy observation. Suppose gcd(a1 , · · · , ad ) = d >
1, then P1 = d1 (a1 , · · · , ad ) ∈ Zd ∩B(O, R) and obviously OB∩B(P1 , r) 6= ∅. 
21
20

Lemma 2. Let l be any ray starting from O, if point P ∈ Zd ∩ B(O, R), P ∈

/l
such that dist(P, l) is minimal, then the coordinates of P are coprime.
 d
4 Leo

ar
Suppose the coordinates of P are coprime with greatest common divisor

Aw
d > 1, then dist( d1 P, l) < dist(P, l). Contradiction. 

To carry out our argument in high dimension, we have to generalize the result
to Lemma 2 from a ray l to a family of geometric objects which we called

ce
diamonds with a diagonal, and is defined as follow:
Definition 1. In Rd , for any positive integer n ≤ d, a n-dimensional diamond

en
D with a diagonal I is defined as follow:
(i) A 1-dimensional diamond D is nothing but a segment start from the

ci
origin O to a point P 6= O in Rd and its diagonal I is itself;
(ii) Suppose for any i ≤ n, the i-dimensional diamonds with a diagonal

lS
are well-defined, then a n-dimensional diamond Dn with a diagonal In
is defined base on some n-dimensional diamond Dn−1 with a diagonal
In−1 : let Vn−1 be the n − 1 vector space generated by vectors in Dn−1 ,

oo
and Pn a point in Rd \Vn−1 , consider OIn−1 and OPn as two vectors,
then define Qn be the end point of the vector OIn−1 − OPn , and Dn
is defined to be the convex hull of Dn−1 ∪ {Pn , Qn }, its diagonal is
h
In := In−1 .
Sc
h
ig
H
au
.Y

Figure 2. an example of 1,2 and 3-diamonds

-T
S.

Lemma 3. Let D be a n-dimensional diamond with a diagonal I in Rd , n < d,

V be n-dimensional subspace in Rd generated by D. Now if a point P ∈ Zd ∩
B(O, R), P ∈
/ V such that dist(P, D) is minimal, then the coordinates of P are
21

coprime.
Suppose A ∈ D is the point such that dist(P, D) = dist(P, A) = a. Consider
20

the triangle ∆OAP , since D is a convex hull by the definition, the segment
OA ⊂ D. Now if the greatest common divisor of the coordinates of P is m > 1,
 d
Orchard Visibility Problem 5

ar
1
consider the point Q = m P ∈ OP . Find a point Q0 ∈ OA ⊂ D such that

Aw
0
QQ k AP , then apparently that dist(Q, D) < dist(P, D). Contradiction! 

Proof of the theorem: Consider the point D1 := D given above, we

ce
view the segment OD as a vector from the origin O to D and denote it by ~l.
Among all integral points in B(O, R), find P2 in the first quadrant (that is,
all the points are of nonnegative coordinates) be the one of minimal distance

en
to ~l. Write the minimal distance ε1 . From the lemmas above, we know the
coordinates of P2 are coprime. View the segment OP2 as a vector and denote
it by ~v1 , and define vector ~u1 := ~l −~v1 , define the two dimensional diamond D2

ci
be the parallelogram spanned by ~v1 and ~u1 . From the two lemmas above, D2

lS
does not contain any integral points of Λ other than the 4 vertices. Denote the
2-dimensional plane spanned by ~v1 and ~u1 by V2 . Using our notion of diamond,
D2 is a 2-dimensional diamond with a diagonal l.

oo
Now among all integral points in B(O, R)\V2 , find one P3 in the first quad-
rant of the minimal distance to V2 ∩ B(O, R). Write the minimal distance ε2 .
h
Consider the 2-dimensional diamond D2 with diagonal ~l and the point P3 , by
Sc

Definition 1, they together define a 3-dimensional diamond D3 with diagonal

~l. By Lemma 3, all the coordinates of P3 are coprime, D3 contains no inte-
gral points other than the 6 vertices. Denote the 3-dimensional vector space
generated by vectors in D3 by V3 .
h
ig

Keep this process, for all integer i = 1, 2, · · · , d, we obtain i-dimensional dia-

mond Di with diagonal ~l, Vi = spanDi , integral points Pi in the first quadrant
H

such that
(a) dist(Pi , Vi−1 ∩ Vi−1 ) = εi−1 is minimal among all integral points in
au

B(O, R)\Vi−1 ;
(b) Di is the diamond constructed by Di−1 and Pi ;
(c) Di contains no integral points other than its vertices.
.Y

It is easy to see, from our construction, the volume of Di is

2i−1
(2.4) V ol(Di ) = ε1 · · · εi−1 ([R] + 1).
i!
-T

In particular, Write D := D − d, its volume is

2d−1
S.

(2.5) V ol(D) = ε1 · · · εd−1 ([R] + 1),

d!
which can also be calculated by Macdonald’s formula as in Proposition 2. On
21

the other hand, By our construction of D, if the tree radius r is such that every
ray starting from O and passing through one point in D will be blocked by
some tree, then r > εi for any i. So we have
20

2d−1 d−1
(2.6) r ([R] + 1) > V ol(D).
d!
 d
6

ar
Writing

Aw
d!V ol(D)
(2.7) c= ,
2d−1
we complete the proof. 

ce
Remark 2. If d = 2, V ol(D) = V ol(D2 ) = 1, then the Theorem tells that

en
([R] + 1)ρ > 1, which reproduces
√ √
the result in [3, Proposition 2.4]. If d = 3,
V ol(D) = V ol(D3 ) = 32 22 22 = 31 , then the theorem tells that
1

ci
(2.8) ([R] + 1)ρ2 >
,
2

lS
which is better than the result in [3, Proposition 4.4].

3. Upper bounds
oo
In this section we give an upper bound of ρ in terms of R. The key ingredient
h
is again Minkowsk’s theorem as [3, Theorem 4.1], which we summarize below.
Sc

Proposition 3 (Minkowski’s Theorem). Let m be a positive integer and F ⊂

Rd a domain satisfying
(a) F is symmetric with respect to O;
h

(b) F is convex;
(c) V ol(F ) ≥ m2d .
ig

Then F contains at least m pairs of points ±Ai ∈ Zd \O, 1 ≤ i ≤ m, which are

H

distinct from each other.

Now we state an upper bound of ρ. The idea is essentially same to [3, §4],
au

where, however, only deals with the 3-dimensional case.

Theorem 2. There is a constant C > 0, such that
.Y

(3.1) Rρd−1 < C.

Proof: For any diameter AA0 of the ball B(O, R), let’s consider the d − 1-
dimensional hyperellipsoid E ⊂ Rd as follow:
-T

(i) AA0 is a long axis of E;

(ii) all other semi-axes of E are equal of length h.
S.

Indeed, consider the function of d variables:

x21 x2 x2
F (x1 , · · · , xd ) := + · · · + d−1 + d2 ,
21

h 2 h 2 R
then F (x1 , · · · , xd ) = 1 gives the hyperellipsoid when AA0 is lying in the xd -
axis. Generally, if the line AA0 has a unit directional vector ~ud , extend it to
20

a orthnormal basis β := {~u1 , · · · , ~ud−1 , ~ud } of Rd . Then there exists a unitary

transformation T : Rd → Rd which sends β to the standard orthnormal basis
 d
Orchard Visibility Problem 7

ar
{(1, 0, · · · , 0), · · · , (0, · · · , 0, 1)} such that T (~ud ) = (0, · · · , 0, 1). Then the d−1-

Aw
dimensional hyperellipsoid E has equation F (T (x1 , · · · , xd )) = 1. See Figure
3.

ce
en
ci
lS
Figure 3
h oo
Now let F ⊂ Rd be the domain enclosed by E (including the points of E).
Apparently, F satisfies the condition (a) and (b) of Minkowski’s Theorem.
Moreover, it is known that the volume of the hyperellipsoid is
Sc

d
π2
(3.2) hd−1 R,
Γ( d2 + 1)
h

here Γ is the gamma function, so

ig

d d d d d
(3.3) Γ( + 1) = Γ( ) = ( − 1) · · · γ0 ,
2 2 2 2 2
H

π
where γ0 = 1 if d is even, γ0 = 2 if d is odd. By Minkowski’s Theorem, if we
choose h such that
au

d
π2
(3.4) d
hd−1 R = 2d ,
Γ( 2 + 1)
.Y

then F contains an integral point other than O. This implies that, if we set
2d Γ( d
2 +1)
1
C = d , and the tree radius r = CR d−1 , then any ray segment OA
π2
-T

starting from O will be blocked by some tree at the integral point contained in
F we constructed as above. Since ρ < r, that we complete the proof. 
S.

Combining Theorem 1 and Theorem 2, we obtain the main result of this article:
Theorem 3. For d-dimensional orchard visibility problem, as the radius of
21

orchard R goes to infinity,

1
(3.5) ρ = O(R− d−1 ).
20
 d
8

ar
4. Some Further Thoughts

Aw
We can still ask a lot of questions concerning the orchard visibility problem
in arbitrary dimension. For example, for d = 2, it has been proved in [2] that
ρ = R1 , or
(4.1) lim ρR = 1.

ce
R→∞
Inspired by our results, it is natural to ask if we can find a constant l for
dimension d such that

en
(4.2) lim ρd−1 R = l.
R→∞

ci
However, our estimation in this article using polyhedra is apparently not precise
and fine enough for such a conclusion. We will explore this problem in the

lS
future.

References

and system sciences, 74 (2008) 587–597.

h oo
[1] Clyde P. Kruskal The orchard visibility problem and some variants, Journal of computer

[2] Thomas Tracy Allen Polya’s Orchard Problem,The American Mathematical Monthly,
Vol. 93, No. 2 (1986) 98-104.
Sc

[3] Alexandru Hening and Michael Kelly On Polya’s Orchard Problem,Rose-Hulman Un-
dergraduate Mathematics Journal: Vol. 7 : Iss. 2 , Article 9.
[4] I. G. Macdonald The volume of a lattice polyhedron, Mathematical Proceedings of the
Cambridge Philosophical Society, 59 (1963) 719-726.
h
ig
H
au
.Y
-T
S.
21
20