Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 35 (1994), No. 2, 149-162.

On a Geometrical Interpretation of a Sampling

Dedicated to Professor J. Horváth on his 60th birthday

László Szalay and Ágota H. Temesvári

Institut für Mathematik, Universität für Forst- und Holzwissenschaft H – 9401 Sopron, Pf. 132, Ungarn

1. Introduction.

Plane sampling methods and related geometrical problems are studied in this paper. Forest surveys, agricultural surveys, soil and geological surveys are some examples for applications of sampling methods. More detailed description of examples can be found in [1] by T. Dalenius, J. Hájek, J. Zubrzycki.

An isotropic plane stochastic process is discussed in [1], when the process is observed in the points of a regular plane pattern. The pattern yielding the least limiting variance of the observed values was searched for. The problem passes over to a density problem related to congruent circles (the centers of circles make up a regular point-system), where the correlation function is (1).

The authors [1] compare some regular systems of points with given density less then \frac{2π}{\sqrt{3}} (regular triangle lattice, rectangular lattice, etc.). They show that the extremum of limiting variance is in general attained not in the case of the regular triangular lattice.

The purpose of our work is to give the extremal system of circles, if their centers form a regular plane lattice. We only deal with system of circles with density not more than \frac{4π}{\sqrt{39}}.

Using the notation of [1], first we sketch the transformation of problem into an equivalent geometrical problem.

2. Notation, definitions.

Now we define a special stochastic process. Let the random variables η(p) belong to the points p of the Euclidean plane. Suppose that the following conditions are satisfied.

(a) All random variables η(p) have a common expected value μ and common variance σ^{2}.

(b) The coefficient of correlation between any two random variables η(p) and η(q) depends only on the vector difference between q and p:

R [η(p), η(q)] = ϱ(q − p).

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix}1994 Heldermann Verlag, Berlin

(c) The correlation function ϱ(p) is continuous, and ϱ(0) = 1.

(d) The process is isotropic, i.e. the correlation function depends only on the length u = |p − q| of the vector p − q. (ϱ(q − p) = ϱ(|q − p|) = ϱ(u).) If

(1)  ϱ(u) = r (\frac{u}{a}) = \{ \begin{matrix}\frac{2}{π} (arccos \frac{u}{a} − \frac{u}{a} \sqrt{1 − (\frac{u}{a})^{2}}) & 0 ≤ u ≤ a; \\ 0 & otherwise; \end{matrix}

where a is a positive number, then it is easy to interpret this case geometrically.

Denote by |K_{1} ∩ K_{2}| the area of common part of two circles K_{1} and K_{2} with radius \frac{a}{2} and centers p_{1} and p_{2} at a distance u = |p_{1} − p_{2}|. It is clear, that

(1^{⋆})  r (\frac{u}{a}) = \frac{|K_{1} ∩ K_{2}|}{\frac{a^{2}π}{4}}.

The mean value of the process is

lim_{|D|→∞} \frac{∫_{D} η(p) dp}{|D|}.

For the unbiased estimation of this mean, η̄ = \frac{1}{n} ∑_{i} η(p_{i}) is used , where the points p_{i} are selected points from the plane. Since

V ar η̄ = \frac{σ^{2}}{n^{2}} ∑_{i} ∑_{j} ϱ(|p_{i} − p_{j}|),

from (1^{⋆}) we obtain

V ar η̄ = \frac{σ^{2}}{n^{2}} \frac{∑_{i} ∑_{j} |K_{i} ∩ K_{j}|}{\frac{a^{2}π}{4}}.

For a sequence of points p_{1}, p_{2},…, p_{n},… the density d is defined as follows:

d = lim_{R→∞} \frac{Card \{i , p_{i} ∈ K(O, R)\}}{R^{2}π}.

Let n_{R} = Card {i , p_{i} ∈ K(O, R)}, and let η̄_{R} be the average of those random variables η(p_{i}) for which p_{i} is in K(O, R). The limiting variance is

σ_{∞}^{2} = lim_{R→∞} n_{R}(V ar η̄_{R}).

The main question is how to select points p_{i} (with given density d), whose limiting variance is a minimum.

Figure 1

From [2] by L. Fejes Tóth, the density of a system of congruent circles with radius \frac{a}{2} is

C′ = lim_{R→∞} \frac{∑_{i} |K_{i} ∩ K(O, R)|}{R^{2}π}.

If the density of the centers p_{i} of circles K_{i} is d, then obviously C′ = |K_{i}|d. In [1] C′ is called mean covering, and the mean double covering C′′ also is defined:

C′′ = lim_{R→∞} \frac{∑_{i} ∑_{j} |K_{i} ∩ K_{j} ∩ K(O, R)|}{R^{2}π}.

In the sequel we only deal with system of points p_{1}, p_{2},…, p_{n},… which are the points of a lattice Γ. The density of a system of circles based on the points p_{i} is constant:

C′ = \frac{\frac{a^{2}π}{4}}{T (Γ)},

where T (Γ) is the area of the fundamental parallelogram P. From the definition of C′′ it

follows that C′′ = ^{\frac{∑_{i} ∑_{j} |K_{i}∩K_{j}∩P|}{T (Γ)}} if the points p_{i} belong to the lattice, and

(2)  C′′ = C′ + \frac{2 ∑_{i} ∑_{j} |K_{i} ∩ K_{j} ∩ P|}{T (Γ)}, i < j.

The origin of the lattice Γ = {O, p_{1},…} will be denoted by O (Figure 1), and the basis {p_{1}, p_{2}} is reduced by Minkowski, i.e.

(3)  |p_{1}| ≤ |p_{2}| ≤ |p_{i}| (i ≠ 1, 2), p_{i} ≠ jp_{1} (z ∈ Z), 0 ≤ α ≤ \frac{π}{2} ,

(α is the angle by p_{1} and p_{2}).

Furthermore we denote by L(Γ, R) the circle arrangement, where Γ is the lattice of centers of circles, and R is the radius of circles. Let k[P_{i}P_{j}P_{k}] be the circumcircle of the triangle P_{i}P_{j}P_{k}, k[P_{i}] the circle with center P_{i} and radius \frac{1}{2}. The radius of the circle k[P_{i}P_{j}P_{k}] is r[P_{i}P_{j}P_{k}]. It is well-known, that

(4)  r = \frac{xyz}{4T} ,

where T is the area of a triangle with sides x, y and z. Lastly we denote the medians of the above triangle by s_{x}, s_{y} and s_{z} .

Let us increase ZX by moving the vertex X on a straight line parallel to the fixed ZY (Figure 2). This is the transformation t_{1}. If ZX = XY, XY can be increased by the transformation t_{2}: the vertex X is ”moving up”, but T does not vary and the equation ZX = XY is satisfied henceforward while ZY decreases.

3. Lemmas.

Lemma 3.1. The correlation function r_{1}(x) = arccos x − x\sqrt{1 − x^{2}}, x ∈ [0, 1] is strictly decreasing and convex.

Proof. Since

(5)  r′_{1}(x) = −2\sqrt{1 − x^{2}} < 0,  x ∈ [0, 1[

thus the statement is obviously true.

Lemma 3.2. Let XY Z any not obtuse angled triangle. Let the sides x, y and z of XY Z_{△} satisfy the inequalities x ≤ y ≤ z ≤ 1. Applying the transformation t_{1} for the triangle XY Z, then for r[XY Z] < \frac{1}{2} the function r_{1}(y) + r_{1}(z) is strictly increasing while for r[XY Z] > \frac{1}{2} it is strictly decreasing.

Proof. Let M be the altitude of the triangle XY Z belonging to the vertex X and S its foot. Denote by v the segment ZS. It easily follows that

y = \sqrt{M^{2} + v^{2}}  and  z = \sqrt{M^{2} + (x − v)^{2}}.

During the moving of X, x and M are constant, v increases. Applying equation (5), the first derivative of the function of p(v) = r_{1}(y(v)) + r_{1}(z(v)) is

p′(v) = −2\sqrt{1 − y^{2}} · y′(v) − 2\sqrt{1 − z^{2}} · z′(v).

If p′ > 0 then we obtain the following inequality

(6/a)  \frac{1}{2} > \frac{xyz}{4 · \frac{1}{2}xM} ,

and in case of p′ < 0

(6/b)  \frac{1}{2} < \frac{xyz}{4 · \frac{1}{2}xM} .

Since the right hand sides of inequalities (6) equal r[XY Z], Lemma 3.2 is proved.

Lemma 3.3. Let the radius of the circumcircle k of an acute angled triangle XY Z with the area T be \frac{1}{2}. If x, y and z are the sides of any triangle inscribed in k, with area T, then

r_{1}(x) + r_{1}(y) + r_{1}(z) = constant.

Proof. Denote by α , β and γ the angles of XY Z (Figure 3). Since r[XY Z] = \frac{1}{2} thus z = sin α , y = sin β , x = sin γ. From α + β + γ = π it follows that

r_{1}(x) + r_{1}(y) + r_{1}(z) = \frac{1}{2} [π − (sin 2α + sin 2β + sin 2γ)] .

In the case of α + β + γ = π

sin 2α + sin 2β + sin 2γ = 4 sin α sin β sin γ

is an identity, and by (4) we have

\frac{1}{2} = \frac{sin α sin β sin γ}{4T} ,

which means that sin α sin β sin γ is constant. Thus r_{1}(x) + r_{1}(y) + r_{1}(z) is also constant.

Lemma 3.4. Let a = AB ≤ b = BC = AC ≤ 1 the sides of the triangle ABC. If the area of ABC_{△} is constant, and a is increasing then

r_{1}(a) + 2r_{1}(b)

is increasing or decreasing according to as r[ABC] < \frac{1}{2} or r[ABC] > \frac{1}{2}.

Because of the similarity to the proof of Lemma 3.2 the proof is not given here.

Lemma 3.5. Let OP_{1} be the length of the shortest basis vector of the lattice Γ, OP_{1} ≤ \frac{1}{3} and \frac{π}{\sqrt{3}} ≤ C′ < \frac{4π}{3\sqrt{3}}. If L(Γ, \frac{1}{2}) is a system of circles with density C′, then C′′ can be minimal only if OP_{1} = \frac{1}{3}.

Proof. If T (Γ) is the area of the fundamental parallelogram of the lattice Γ then \frac{3\sqrt{3}}{16} < T (Γ) ≤ \frac{\sqrt{3}}{4}. Let the vectors O⃗P_{1}, O⃗P_{2} form a Minkowski reduced basis. Let M be the altitude belonging to OP_{1} in the triangle OP_{1}P_{2}.

It will be proved that r[OP_{1}P_{2}] > \frac{1}{2}. Let OP_{1} and T (Γ) be constant. It is clear that r[OP_{1}P_{2}] is minimal for OP_{2} = P_{1}P_{2}. Let r_{s} denote the radius r[OP_{1}P_{2}] in this ”symmetric” case. Since

M = r_{s} + \sqrt{r_{s}^{2} − \frac{OP_{1}^{2}}{4}} ,

we must show that

M > \frac{1}{2} + \sqrt{\frac{1}{4} − \frac{OP_{1}^{2}}{4}} .

We obtain

4T^{2}(Γ) − 4T (Γ)a + a^{4} > 0

by equivalent conversion. It is easy to see that the function 4T^{2}(Γ)−4T (Γ)a+a^{4} is minimal for a = \frac{1}{3}. Its minimum is positive which means r[OP_{1}P_{2}] > \frac{1}{2}.

We use the transformation t_{1} to move P_{2} on the straight line parallel to the fixed OP_{1}. (Of course T (Γ) also is constant.) If P_{1}P_{2} ≥ 1 then the area of k(O) ∩ k(P_{2}) is decreasing. By Lemma 3.2, if P_{1}P_{2} < 1 then |k(O)∩k(P_{2})|+|k(P_{1})∩k(P_{2})| is decreasing. Using (2), C′′ is also decreasing. (There are no other intersections between circles and the fundamental parallelogram.) Finally, by decreasing C′′ we obtain a lattice with OP_{1} = OP_{2}. From the above statements r[OP_{1}P_{2}] > \frac{1}{2} also holds in this ”symmetric” case. Preserving the area T (Γ) and OP_{1} = OP_{2}, now we increase OP_{1} (the inverse transformation of t_{2}). For circles whose centers lie on the line OP_{1}, the sum of areas of the pairwise intersections is thus reduced. Using Lemma 3.4, if OP_{2} < 1 then C′′ will be reduced during the transformation mentioned above. At the end OP_{1} reaches \frac{1}{3}. The proof of Lemma 3.5 is completed.

Lemma 3.6. If x ≤ y = z for the sides of a triangle XY Z and \frac{1}{6} < T ≤ \frac{\sqrt{3}}{4} for its area T are satisfied then s_{y} > \frac{1}{2} for the median s_{y} belonging to the side y.

Proof. The median s_{y} is

s_{y} = \frac{1}{2}\sqrt{\frac{9}{4}x^{2} + \frac{4T^{2}}{x^{2}}} .

s_{y} > \frac{1}{2} if and only if

(7)  9x^{4} − 4x^{2} + 16T^{2} > 0.

Since the discriminant of 9x^{4} − 4x^{2} + 16T^{2} is negative, (7) is satisfied.

Lemma 3.7. Let the shortest basis vector O⃗P_{1} of the lattice Γ have length OP_{1} ≥ \frac{1}{2}. If \frac{π}{\sqrt{3}} ≤ C′ < \frac{3π}{4} , then the double-density C′′ of the circle arrangement L(Γ, \frac{1}{2}) with density

C′ can be minimal only in the case |O⃗P_{1}| = \frac{1}{2}.

Proof. Let O⃗P_{1} and O⃗P_{2} be the basis vectors of the lattice Γ, reduced in the sence of Minkowski. The area of its fundamental parallelogram is T (Γ) = xM, where x = |O⃗P_{1}|. Since T (Γ) ≤ \frac{\sqrt{3}}{4} and x ≥ \frac{1}{2} thus M ≤ \frac{\sqrt{3}}{2}. Then M ≥ x\frac{\sqrt{3}}{2} on the basis of (3), and x ≤ \frac{\sqrt{2}}{2} follows from T (Γ) ≤ \frac{\sqrt{3}}{4}.

If r[OP_{1}P_{2}] ≥ \frac{1}{2}, then xM ≥ x\sqrt{1 − x^{2}}. Therefore \frac{\sqrt{3}}{4} ≥ x\sqrt{1 − x^{2}}, which is satisfied only for x = \frac{1}{2} because of \frac{1}{2} ≤ x ≤ \frac{\sqrt{2}}{2}. In this case M = \frac{\sqrt{3}}{2} , C′ = \frac{π}{\sqrt{3}} and r[OP_{1}P_{2}] = \frac{1}{2}.

We can suppose that r[OP_{1}P_{2}] ≤ \frac{1}{2}. What kind of circle pairs can occur in C′′? It is sufficient to examine a fundamental parallelogram of the lattice. We have k(P_{2}) ∩ k(P_{1} − P_{2}) = ∅ because of \frac{1}{2} ≤ x ≤ \frac{\sqrt{2}}{2} and \sqrt{1 − x^{2}} ≤ M (Figure 4).

Lemma 3.6 shows that k(P_{1}) ∩ k(−P_{1} + P_{2}) = ∅. Therefore the intersections k(O) ∩ k(P_{1}), k(O) ∩ k(P_{2}), k(P_{1}) ∩ k(P_{2}), k(O) ∩ k(P_{1} + P_{2}) are possible in C′′ in the case i ≠ j. Since r[OP_{1}P_{2}] ≤ \frac{1}{2} the first three intersections are not equal to the empty set. Let y and

Figure 4

z denote OP_{2} and P_{1}P_{2}. k(O) ∩ k(P_{1} + P_{2}) ≠ ∅ if the median s_{z} of the triangle OP_{1}P_{2} is ≤ 1.

We consider the following lattice transformation t_{3}. The lattice line P_{1}P_{2} is fixed and O runs on a line parallel to P_{1}P_{2} by decreasing of x. Using t_{3} the median s_{z} increases and r_{1}(2s_{z}) decreases for 2s_{z} < \frac{1}{2}. It is clear that r_{1}(z) is constant. r_{1}(x) + r_{1}(y) decreases for r[OP_{1}P_{2}] ≤ \frac{1}{2} according to Lemma 3.2. That means that by application of t_{3} we obtain such circle arrangements for which C′′ decreases.

Finally we have the case x = \frac{1}{2} or y = z. (The case r[OP_{1}P_{2}] = \frac{1}{2} is possible only for x = \frac{1}{2} and C′ = \frac{π}{\sqrt{3}}.) If y = z then 2s_{z} > 1 according to the Lemma 3.6. In this case we use the inverse transformation of t_{2} and we continue to decrease C′′.

Thus finally we reach the case x = \frac{1}{2}.

Lemma 3.8. Let \frac{π}{\sqrt{3}} ≤ C′ ≤ \frac{4π}{\sqrt{39}}. Let (3) hold for the lattice triangle OP_{1}P_{2} of Γ and let the length of the median belonging to P_{1}P_{2} be no more than \frac{1}{2}. If r[OP_{1}P_{2}] < \frac{1}{2}, then the function R_{1} = r_{1}(OP_{2}) + r_{1}(P_{1}P_{2}) + r_{1} (O(P_{1} + P_{2})) monotonically increases by using the transformation t_{1} with the notation X = P_{2}, Z = O, Y = P_{1}.

Proof. First we will show in 3.8.1 that the statement of Lemma 3.8 is true for C′ = \frac{4π}{\sqrt{39}}. Then we will prove in 3.8.2 that if the derivative of R_{1} is positive for some C′_{1} in this interval then it is also positive for all C′ with \frac{π}{3} ≤ C′ < C′_{1}.

3.8.1. We take the lattice triangle OP_{1}P_{2} and use the notation of Figure 2. Let X = P_{2} , Y = P_{1} and Z = O. Then we obtain

(8)  R′_{1}(v) = −2\sqrt{1 − y^{2}} \frac{v}{y} + 2\sqrt{1 − z^{2}} \frac{x − v}{z} − 2\sqrt{1 − (2s_{z})^{2}} \frac{x + v}{2s_{z}} .

Equivalently we have

(9)  R′_{1}(v) = 4v \{\frac{2x (1 − \frac{M^{2}}{z^{2}(2s_{z})^{2}} )}{f(z) + f(2s_{z})} − \frac{(1 − y^{2})\frac{v}{y^{2}}}{2f(y)} \} ,

where f(s) = \sqrt{1 + M^{2} − s^{2} − M^{2}/s^{2}}.

We have

(10)  \frac{f(z) + f(2s_{z})}{2} ≤ \sqrt{\frac{f^{2}(z) + f^{2}(2s_{z})}{2}}

because of the inequality between the arithmetic and quadratic means. We will show that

(11)  \sqrt{\frac{f^{2}(z) + f^{2}(2s_{z})}{2}} ≤ f(y).

(11) is namely equivalent to the inequality

(12)  0 < −x(x − 2v) (\frac{M^{2}}{y^{2}z^{2}} − 1) + x(x + 2v) (1 − \frac{M^{2}}{y^{2}(2s_{z})^{2}} ) .

There follows \frac{M^{2}}{y^{2}z^{2}} − 1 > 0 from r[OP_{1}P_{2}] < \frac{1}{2} (cf.(4)). Since x, v > 0 it is sufficient to show that

(13)  1 − \frac{M^{2}}{y^{2}(2s_{z})^{2}} > \frac{M^{2}}{y^{2}z^{2}} − 1.

(13) is equivalent to

(14)  y^{2}z^{2}(2s_{z})^{2} > 2M^{2}xv.

It is easy to see that z^{2}(2s_{z})^{2} > 2xv. Because of (3), y^{2} ≥ M^{2} is satisfied, i.e. (14) and with this also (12) is true.

We obtain v ≤ \sqrt{1 − M^{2}} − x from 2s_{z} ≤ 1. It is easy to see that \sqrt{1 − M^{2}} − x ≤ \frac{x}{4}, that means v ≤ \frac{x}{4}. It is to show that the inequality

(15)  2x (1 − \frac{M^{2}}{z^{2}(2s_{z})^{2}} ) > \frac{v}{y^{2}} (1 − y^{2})

is satisfied.

Combining (10),(11) and (12) we see that R′_{1}(v) > 0 in (8) which was to be proved. 3.8.2. We have \frac{\sqrt{39}}{16} ≤ T (Γ) ≤ \frac{\sqrt{3}}{4} from \frac{π}{\sqrt{3}} ≤ C′ ≤ \frac{4π}{\sqrt{39}}. We will prove that R′_{1} is a

monotonously increasing function of M in the case of fixed x and v.

Let Q_{1}(M) = R′_{1}(v). Then

Q′_{1}(M) = 2 \{\frac{vM}{y^{3}\sqrt{1 − y^{2}}} − \frac{(x − v)M}{z^{3}\sqrt{1 − z^{2}}} + \frac{(x + v)M}{(2s_{z})^{3}\sqrt{1 − (2s_{z})^{2}}} \} .

It is to be shown that z ≥ \frac{\sqrt{3}}{2}. In this case the function

a ⟼ a^{3}\sqrt{1 − a^{2}}, a ∈ [\frac{\sqrt{3}}{2}, 1]

is monotonously increasing, i.e.

z^{3}\sqrt{1 − z^{2}} ≥ (2s_{z})^{3}\sqrt{1 − (2s_{z})^{2}}.

It follows that Q′_{1}(M) ≥ 0 and Q′(M) = 0 only in the case v = 0 (^{}P̸_{1}OP_{2} = \frac{π}{2} ).

Lemma 3.9. Suppose that x ≤ \frac{1}{2} and x ≤ y ≤ z ≤ 1 are satisfied for the sides x , y, z of the right angled triangle XY Z and that \frac{\sqrt{6}}{12} ≤ T ≤ \frac{\sqrt{3}}{8} holds for its area. If T is constant then the function

L(x) = r_{1}(x) + r_{1}(2x) + r_{1}(y) + 2r_{1}(z)

has only one minimum.

Proof. There follows \frac{1−\sqrt{1−16T^{2}}}{2} ≤ x^{2} from z ≤ 1. We take the derivative of L(x) with respect to x. Then

(16)  L′(x) = −2\sqrt{1 − x^{2}} − 4\sqrt{1 − (2x)^{2}} − 2\sqrt{1 − y^{2}}y′(x) − 2\sqrt{1 − z^{2}}z′(x).

We have y′(x) = −\frac{2T}{x^{2}} and z′(x) = \frac{x^{4}−4T^{2}}{z(x)·x^{3}} , because of y(x) = \frac{2T}{x} and z(x) = = x^{2} + \frac{4T^{2}}{x^{2}} , where x^{4} − 4T^{2} < 0 (because of the conditions).

It is easy to show that L′ (\sqrt{\frac{1−\sqrt{1−(4T)^{2}}}{2}} ) < 0 and L′ (\frac{1}{2}) > 0. The negative sum of

the negative terms 2\sqrt{1 − x^{2}} + 4\sqrt{1 − 4x^{2}} decreases monotonically. The reader can readily verify that −2\sqrt{1 − z^{2}}z′(x) = 2\sqrt{1 − z^{2}} \frac{4T^{2}−x^{4}}{z(x)·x^{3}} and −2\sqrt{1 − y^{2}} y′(x) = 2\sqrt{1 − y^{2}} \frac{2T}{x^{2}} are positive and monotonically increasing.

It follows from the foregoing that the function has a single zero, that means L(x) has only one minimum.

4. Results.

In this section we give the lattices depending on C′ for which C′′ is minimal. The sampling is the most favourable for these lattices if we take all the lattices with fixed density. We can calculate the extremal double-densities C′′ with knowledge of the extremal lattices. We can assume that the radius of circles is \frac{1}{2}.

4.1. In the case C′ < \frac{π}{2\sqrt{3}} the minimum of C′′ is C′. There are an infinite number of extremal lattices, among others the regular triangular lattice.

Proof. We can give such lattice arrangements of circles with radius \frac{1}{2} for fixed C′ which are packings. This means each point of the plane belongs to at most one of the circles. It is clear that C′′ = C′ and C′′ is minimal (cf.(2)).

4.2 The regular triangular lattice is extremal for the densities \frac{π}{2\sqrt{3}} ≤ C′ ≤ \frac{2π}{3\sqrt{3}}.

Proof. We can assume that the base of the lattice Γ of the circle arrangement with density C′ is reduced by Minkowski. This means that the base vectors p_{1} and p_{2} of Γ (Figure 5) satisfy the inequalities (3). First we prove that r[OP_{1}P_{2}] > \frac{1}{2}. We know that the regular triangle has the maximal area among the triangles inscribed in the circle k[OP_{1}P_{2}]. This means that the radius of the circumscribed circle of the triangle with area \frac{T (Γ)}{2} is less then r[OP_{1}P_{2}]. If we take a regular lattice triangle in this density interval then the radius of the circumsribed circle is greater than \frac{1}{2}.

Figure 5

Let X = P_{1} , Z = O , Y = P_{2}. We apply the transformation t_{1}. Since r[OP_{1}P_{2}] > \frac{1}{2} therefore Σ = r_{1}(|p_{2}|)+r_{1}(|p_{2} −p_{1}|)+r_{1}(|p_{1}|) decreases on the basis of Lemma 3.2. Finally we reach the case |p_{2}| = |p_{1} − p_{2}|. The radius r[OP_{1}P_{2}] decreases also but it remains greater than \frac{1}{2}. We have an isosceles triangle and we can use the transformation described in Lemma 3.4. Since the radius of the circumscribed circle is greater than \frac{1}{2}, Σ decreases, using the above transformation. At the end we have the case |p_{1}| = |p_{2}| = |p_{2} − p_{1}|, i.e. the regular triangular lattice (Figure 6).

The sum of the areas of the intersections k(O)∩k(P_{1}) , k(P_{1})∩k(P_{2}) and k(O)∩k(P_{2}) is minimal for the regular triangular lattice. In this case there are only at most 2-fold covered parts in the plane, this means that only \frac{2Σ}{T (Γ)} occurs in (2) in the second term.

Figure 6

It follows from the above mentioned that C′′ is minimal for the regular triangular lattice.

Remark. The statement 4.2 can also be proved by using an inequality in [2] (Fejes Tóth, inequality (3), p.80).

4.3. If \frac{2π}{3\sqrt{3}} < C′ < \frac{π}{\sqrt{3}} then C′′ is minimal for an infinite number of lattices. The base vectors of these lattices satisfy (3) and

(17)  \frac{1}{2} ≤ |p_{1}|, r[OP_{1}P_{2}] = \frac{1}{2} and T (Γ) = \frac{π}{4C′} .

Proof. We distinguish three different cases depending on the radius of the circumscribed circle of the lattice triangle OP_{1}P_{2}.

4.3.1. Let r[OP_{1}P_{2}] = \frac{1}{2}. If conditions (17) are fullfilled, then C′′ has the same value for all of these lattices according to Lemma 3.3 (Figure 7). It is easy to see that C′′ is greater for OP_{1} < \frac{1}{2} than in the case OP_{1} ≥ \frac{1}{2}.

4.3.2. If r[OP_{1}P_{2}] > \frac{1}{2} then we have the following possible intersections of our circles: k(O)∩k(P_{2}), k(P_{1})∩k(P_{2}), k(O)∩k(P_{1}) and further circle pairs with centers on the lattice line OP_{1} can have non-empty intersections.

We use the transformation t_{1} and move the point P_{2} parallel to OP_{1} by increasing OP_{2}. Then C′′ decreases on the base of Lemma 3.2. It is clear that r[OP_{1}P_{2}] decreases too. Finally we have either r[OP_{1}P_{2}] = \frac{1}{2} (4.3.1) or OP_{1} = P_{1}P_{2}. In the second case C′′ decreases according to Lemma 3.4, if we use the transformation t_{2} with notations A = O , B = P_{1} and C = P_{2}. The side OP_{1} increases and at the end we have either r[OP_{1}P_{2}] = \frac{1}{2} (4.3.1) or OP_{1} = OP_{2} = P_{1}P_{2} (only for C′ = \frac{2π}{3\sqrt{3}}).

4.3.3. Let r[OP_{1}P_{2}] < \frac{1}{2}. It is easy to show that P_{1}P_{2} > 1 for OP_{1} ≤ \frac{1}{2} and ^{}P̸_{1}OP_{2} = \frac{π}{2} . This means that O(P_{1} + P_{2}) > 1, i.e. k(O) ∩ k(P_{1} + P_{2}) = ∅. In the case OP_{1} ≤ \frac{1}{2} we use

Figure 7

the inverse transformation of t_{1}. C′′ decreases according to Lemmas 3.2 and 3.4, and the reader can readily verify, that for x > \frac{1}{2} C′′ can be mimimal either in the case OP_{1} = \frac{1}{2} or for r[OP_{1}P_{2}] = \frac{1}{2}.

4.4 In the case \frac{π}{\sqrt{3}} ≤ C′ ≤ \frac{4π}{\sqrt{39}} there is only one lattice Γ, for which C′′ is minimal. The angle P_{1}OP_{2} is \frac{π}{2} and x = OP_{1} satisfies the equality L′(x) = 0 (cf.(16)).

Proof. We can assume on the basis of Lemmas 3.5 and 3.7, that \frac{1}{3} ≤ OP_{1} ≤ \frac{1}{2} is satisfied for the shortest lattice vector OP_{1} of Γ. The intersections k(O) ∩ k(P_{1}), k(O) ∩ k(2P_{1}), k(O) ∩ k(P_{2}), k(P_{1}) ∩ k(P_{2}) and k(O) ∩ k(P_{1} + P_{2}) (Figure 4) only are possible in this density interval since k(P_{1}) ∩ k(−P_{1} + P_{2}) = ∅ according to Lemma 3.6.

4.4.1. Let us consider the case r[OP_{1}P_{2}] ≥ \frac{1}{2}. We use the lattice transformation t_{1} with notations X = P_{2}, Z = O, Y = P_{1}. We have k(O) ∩ k(P_{1} + P_{2}) = ∅ because of 2s_{z} ≥ z. The sum r_{1}(y) + r_{1}(z) decreases according to Lemma 3.2, and r_{1}(x) is constant. This means C′′ decreases by using t_{1}. The radius r[OP_{1}P_{2}] also decreases. Finally we have either r[OP_{1}P_{2}] = \frac{1}{2} or OP_{1} = P_{1}P_{2} and r[OP_{1}P_{2}] > > \frac{1}{2}. In the second case, if we use the lattice transformation t_{2}, then C′′ decreases (Lemma 3.4). Since x = OP_{1} increases we reach either x = \frac{1}{2} or r[OP_{1}P_{2}] = \frac{1}{2}. x = \frac{1}{2} with r[OP_{1}P_{2}] > \frac{1}{2} is not possible. Namely we have M ≤ \frac{\sqrt{3}}{2} because of T (Γ) = \frac{1}{2}M ≤ \frac{\sqrt{3}}{4}. The radius r[OP_{1}P_{2}] is maximal for M = \frac{\sqrt{3}}{2} and its maximum is \frac{1}{2}. The minimum of C′′ can only be attained for r[OP_{1}P_{2}] = \frac{1}{2} (see Figure 8).

Let Γ̄ denote the rectangular lattice with r[OP_{1}P_{2}] = \frac{1}{2} and with the given determinant T (Γ). Let x̄ be the length of the shortest basis vector. It can be shown that

\sqrt{\frac{3−\sqrt{5}}{6}} ≤ x̄ ≤ \frac{1}{2}. It is clear that x < x̄ holds for an arbitrary lattice with area T (Γ) and r[OP_{1}P_{2}] = \frac{1}{2}. The function r_{1}(x) + r_{1}(y) + r_{1}(z) is constant. If x increases then r_{1}(2x) decreases and r_{1}(2s_{z}) = 0 in the case x = x̄. This means that C′′ will be minimal for Γ̄.

4.4.2. If r[OP_{1}P_{2}] < \frac{1}{2} then k(O)∩k(P_{1} +P_{2}) ≠ ∅ can also occur. Let us use the inverse of

Figure 8

t_{1}. Then C′′ decreases on the basis of Lemmas 3.2 and 3.8. The radius r[OP_{1}P_{2}] increases and finally we have either the case r[OP_{1}P_{2}] = \frac{1}{2} or ^{}P̸_{1}OP_{2} = \frac{π}{2} and r[OP_{1}P_{2}] ≤ \frac{1}{2}.

In summary, the extremal lattice has the properties ^{}P̸_{1}OP_{2} = \frac{π}{2} and r[OP_{1}P_{2}] ≤ \frac{1}{2} (Figure 8). There is only one extremal among these lattices on the basis of Lemma 3.9. The length of x = OP_{1} is the solution of the equation L′(x) = 0 (cf.(16)).

Remark. Investigations by computer suggest that the extremal lattice is rectangular also for \frac{4π}{\sqrt{39}} < C′ < \frac{4π}{3\sqrt{3}}. If C′ > \frac{4π}{\sqrt{39}}, then we have more intersections of circle pairs. This leads to serious analytical difficulties.

References.

[1] Dalenius, T.; Hájek, S.; Zubrzycki, S.: Plane sampling and related geometrical problems, Proc. 4th Berkeley Symposium on Mathematical Statistics and Probability 1961, Vol.I., 125-150.

[2] Fejes Tóth, L.: Lagerungen in der Ebene, auf der Kugel und im Raum, Berlin– Göttingen–Heidelberg, Springer 1972.

Received, December 11, 1993; revised version, March 1994.