Issues of Geometric Description of Discrete Structures

I. E. Naats

(Presented by the scientific seminar of the computing laboratory)

Certain questions in the study of the physical properties of bodies that, from a definite point of view, form discrete structures lead to the need to study the geometric properties of these structures. In particular, such questions include the study of radiation damage to a crystal lattice and the defectoscopy of concrete products (pebble-cement). Accordingly, there arises the need to introduce characteristics in terms of which an unambiguous and complete description of the geometric properties of the discrete structures forming the body under investigation is possible. The construction of such characteristics is the subject of the present work.

It is known that, to describe a solid body as a discrete structure, one uses the geometric model of filling Euclidean space with spheres [1]. An analogous model, within certain limits, may be applied in studying the structure of concrete products, and in particular the distribution of coarse aggregate as a system of convex bodies in the volume of the product. Using a geometric model of the structure, one can approach the question of constructing characteristics for describing its geometric properties.

In the filling problem, an important characteristic is the density of filling \(\rho\) of a volume \(V\) in Euclidean space by a system of convex bodies \(\{v_i\}\) \((i=1,2\ldots N)\), which is defined as the ratio of the filled space in the volume of the body to the volume of this body [2], i.e.

\[ \rho=\frac{1}{V}\sum_{i=1}^{N} v_i . \tag{1} \]

The density of filling physically characterizes the degree of homogeneity of a discrete structure. In the case of spheres, the system \(\{v_i\}\) \((i=1,2\ldots N)\) does not form a system of substituting bodies; therefore \(\sum_{i=1}^{N} v_i < V\) and \(0<\rho<1\). Accordingly, the inhomogeneity of the body (structure) can be characterized by the quantity \((1-\rho)\), which in meaning is the ratio of the volume of unoccupied space \(\left(V-\sum_{i=1}^{N} v_i\right)\) in the volume of the body to the volume of this body. The dens-

the filling density \(\rho\) is an integral characteristic, i.e., it characterizes the structure as a whole.

To estimate the local distribution of filler bodies over the volume of the body under study—which is especially necessary in problems of determining a structural defect in one sense or another—it is convenient to introduce a coefficient of linear homogeneity. Mathematically, the coefficient of linear homogeneity (for simplicity we consider filling in a plane) can be defined as the ratio of the sum of the segments of the ray trajectory enclosed within the filler bodies to the thickness of the body, i.e.,

\[ l=\frac{1}{a}\sum_{k=1}^{M} a_k, \tag{2} \]

where the notation is: \(a\) is the thickness of the body, \(a_k\) is the length of the segment inside the \(k\)-th filler body on the ray trajectory (Fig. 1, a), and \(M\) is the number of filler bodies intersected by the ray in the given direction.

The coefficient of linear homogeneity changes under parallel displacement of the ray, thereby characterizing the local distribution of homogeneity (respectively, inhomogeneity) along the length of the body under study in a fixed direction.

Let us consider in more detail the filling of a rectangular region in the plane. In a direction parallel to the \(y\)-axis (Fig. 1, b), the coefficient of linear homogeneity \(l\) is a function of \(x\), i.e., one may introduce the notation \(l_y(x)\). In an entirely analogous way, one may consider the coefficient of linear homogeneity in the direction of the \(x\)-axis as a function \(l_x(y)\). The following assertion is valid: the mean value of the function \(l(x)\) over the length of the body \(b\) \((0\le x\le b)\) is equal to the filling density \(\rho\) of this body, i.e.,

\[ \frac{1}{b}\int_{0}^{b} l_y(x)\,dx=\rho. \tag{3} \]

Fig. 1. \(a\) — example of a discrete structure in the plane;
\(b\) — curve of the distribution of linear homogeneity for the given example

The validity of the assertion is proved by substituting (2) into (3), taking into account that in the present example

\[ a_k(x)= \begin{cases} 2\sqrt{R^2-(x-x_k)^2}, & \text{for } (x-x_k)<R,\\ 0, & \text{for } (x-x_k)\ge R, \end{cases} \tag{4} \]

where \(R\) is the radius of the circle.

The importance of relation (3) consists in the fact that it makes possible a practical determination of the quantity \(\rho\), since the values of the coefficient \(l\) can be obtained experimentally by radiation methods. In turn, the quantity \(\rho\) determines the physical properties of the body under study. Note that relation (3) is valid for bodies of any shape and for any direction.

In conclusion, let us consider the geometric properties of the simplest discrete structure: a set of circles in the plane filling a rectangular strip in \(n\) densely packed layers \((0\le x\le b,\ b\gg 2R)\). For such a region [2] \(\rho\le 0.9069\ldots\), where equality is attained on a strip of infinite dimensions. Let us find an estimate of the greatest and least values of \(l_y(x)\) for \(0\le x\le b\). Constructing a system of substituting regular hexagonal cells circumscribed about the filling circles, it is not difficult to calculate that, in the plane,

\[ \max_{0\le x\le b}\ \sum_{i\in I(x)} a_k=\frac{\sqrt{3}}{2}\,nD, \tag{6} \]

where \(D\) is the diameter of a circle and \(I(x)\) is the set of indices of the circles intersected by a ray in the direction parallel to the \(y\)-axis from the point \(x\) (Fig. 1). Correspondingly, we find

\[ \min_{0\le x\le b}\ \sum_{i\in I(x)} a_k= \begin{cases} \dfrac{nD}{2}, & \text{for even } n,\\[6pt] \dfrac{(n-1)D}{2}, & \text{for odd } n. \end{cases} \tag{7} \]

It is not difficult to calculate the width of a strip composed of \(n\) layers of densely packed circles:

\[ d_n=nD\left[\frac{\sqrt{3}}{2}+\frac{2-\sqrt{3}}{2n}\right]. \tag{8} \]

For large \(n\) one may use the approximate equality

\[ d_n=\frac{nD\sqrt{3}}{2}. \tag{9} \]

Using (6) and (8), we find

\[ l_{\max}=\frac{1}{1+\dfrac{2-\sqrt{3}}{\sqrt{3}\,n}}. \tag{10} \]

As \(n\to\infty\), we obtain the limiting value for the maximum value of the homogeneity coefficient:

\[ \lim_{n\to\infty} l_{\max}=1. \tag{11} \]

Similarly, we have the relations

\[ l_{\min}=\frac{1}{\sqrt{3}+\dfrac{2-\sqrt{3}}{n}}. \tag{12} \]

\[ \lim_{n\to\infty} l_{\min}=\frac{1}{\sqrt{3}}. \tag{13} \]

Thus, for an \(n\)-layer system of densely packed circles, the value of the linear homogeneity coefficient lies in the interval \([l_{\min}(n),\, l_{\max}(n)]\). From (6) and (7) it follows that for any \(n\)

\[ \frac{l_{\min}}{l_{\max}} \leq \frac{1}{\sqrt{3}}, \tag{14} \]

with equality attained for even \(n\).

The set of circles considered forms, in the plane, a regular conformable system that densely fills a rectangular region. Therefore, the obtained values of the geometric characteristics make it possible to judge the values of the corresponding geometric characteristics for an arbitrary filling of rectangular regions by a system of equal circles, i.e., for a set of packings that do not have extremal properties in terms of filling density. In particular, \(l_{\max}\) gives the lower bound of possible values, and \(l_{\min}\) the upper bound.

A similar analysis can be carried out for dense packings in three-dimensional space; however, the computations then become more complicated.

REFERENCES

1. J. C. Slater. Chemical Bonding and Structure. Mir, Moscow, 1966.

2. L. Fejes Tóth. Regular Figures on the Plane, on the Sphere, and in Space. Fizmatgiz, Moscow, 1958.