Name: Masaharu Tanemura, Statistical Scientist, (b. Shiga, Japan, 1946).

Address: The Institute of Statistical Mathematics, 4-6-7 Minami-Azabu, Minato-ku, Tokyo 106-8569, Japan

E-mail: tanemura@ism.ac.jp

Fields of interest: Geometry, spatial statistics, mathematical crystallography.
 
 

Abstract: Statistical properties of geometrical characteristics concerning the random Voronoi Cells, namely, the Voronoi cells for the homogeneous Poisson point processes, are numerically obtained in two-, three- and four-dimensional spaces based on the computer experiments. In this paper, ten million, five-million and five million independent samples of Voronoi cells in two-, three- and four-dimensional spaces, respectively, are generated. Geometrical characteristics such as the cell volume, cell surface area and so on, are fitted to the generalized gamma distribution (GGD). Then, maximum likelihood estimates of parameters of GGD are given. Finally, the relation between the estimated parameters for volume distribution and the dimensionality of space is discussed.
 
 

1. POISSON VORONOI CELLS

Tessellation of space into convex polyhedra is often an interesting theme of the research of symmetry. A typical symmetric case would be the tiling by a single polyhedron. We are interested here the Voronoi tessellation for a completely random configuration of points. Our concern in this paper is therefore the counter example of symmetric case, namely, a typical case of dissymmetry.

We define the Poisson Voronoi cell as the typical Voronoi cell of Voronoi tessellation for the completely random configuration of points, in other words, for the homogeneous Poisson point processes.

From the point of view of application, the Voronoi cells are very useful as a geometrical model of crystal grains, biological cells, and so on. Voronoi cells are also useful as a tool for numerical computations. for the homogeneous Poisson point processes. Hence, it is important to know the statistical properties of Poisson Voronoi cells in order to compare the properties of Voronoi cells for other point patterns.

In spite of the above importance, the statistical properties of Poisson Voronoi cells are not much investigated, mainlly because it is difficult to get them theoretically. We are thus inevitable to take the approach by computer simulations. There are many efforts in this direction. Among them, Hinde and Miles (1980) have conducted a computer simulation of Poisson Voronoi cells in two dimensional  (2-D) space. The sample size of their simulation was two million, which had been a record until now. As the characteristics of Poisson Voronoi polygons, Hinde and Miles (1980) reported the number of edges N, the area A, the perimeter S and so on, and then fitted their histograms to the three parameter generalized gamma density. In case of three dimensional Poisson Voronoi cells, Tanemura (1988) reported the distributions of the volume V and the number of faces F based on a hundred thousand samples of Voronoi polyhedra. More recently, Kumar et al. (1992) presented the results of properties of three-dimensioanl Poisson Voronoi tessellation based on the 358,000 simulated cells. They reported on the statistical properties of F, V, S (surface area) of a Poisson Voronoi polyhedron and fitted their histograms to the two parameter generalized gamma density. We do not know the simulation results of Poisson Voronoi cells for more than four dimensions.
 
 

2. METHOD

In order to make independent samples of Voronoi cells for homogeneous Poisson processes, we use the following method. Although the two-dimensional terminology is used, the extension to other dimensions will be easy.

First, let R be the region where the generating points are distributed, |R| be the area of the region. Let r be the intensity of the Poisson point process. We generate a homogeneous Poisson point pattern inside R with intensity  r. Then, the number of points inside R will obey the Poisson distribution with mean  r|R|. Next, we select the point which is nearest to the center of R and construct a Voronoi cell of the selected point. The procedure is basically due to Hinde and Miles (1980). In Hinde and Miles (1980), they have set  r = 100 in two-dimensional (2-D) case. In the present simulations, we set r = 200; 500 and 1200 for 2-D, 3-D and 4-D spaces, respectively.

In order to compute the central Voronoi cell such as shown in Fig.1, the algorithm devised by Tanemura, Ogawa and Ogita (1983) is the most suitable. In their algorithm, all of the Delaunay triangles which include the central point as a vertex are efficiently constructed. The algorithm is also easy to extend to higher dimensions.
 

3. RESULTS 

In the present work, we have done computer simulations of Poisson Voronoi cells in 2-D, 3-D and 4-D spaces. The numbers of independent samples generated were n = 10; 000; 000 (2-D) and n = 5; 000; 000 (3-D, 4-D). These sample sizes are the biggest among the computer simulations so far reported.

In order to see how our computer simulations work well, we first give the mean value of observed number of (d-1)-facets for each of d = 2; 3; 4 together with its corresponding theoretical value as follows:
 
 

Next, we show the results of the area, volume and hyper-volume of Poisson Voronoi cells in 2-D, 3-D and 4-D, respectively. Figure 2 shows their observed histograms in the same diagram. In these histograms, the reduced volume v = rV is computed where V is the volume of a Voronoi cell for the Poisson point process with intensity r.

As the analysis of the observation, we estimated parameters of the following distribution (three-parameter generalized gamma distribution).

by fitting it to each of the observed histograms as follows: 
 

Here, the exact values for d = 1are well known.

From the above table. we immediately note that there might exist some relationship among parameters with the dimensionality of space. It might be said that the tendency will be ‘dissymmetric’. Thus, it will be interesting to investigate the Poisson Voronoi cells in more higher dimensions.

References

Christ, N.H., Friedberg, R. and Lee, T.D. (1982) Random lattice field theory: General formulation. Nuclear Physics, B202, 89 – 125.

Hinde, A.L. and Miles, R.E. (1980) Monte Carlo estimates of the distributions of the random polygons of the Voronoi tessellation with respect to a Poisson process. Journal of Statistical Comptutation and Simulation, 10, 205–223.

Kumar, S., Kurtz, S.K., Banavar, J.R. and Sharma, M.G. (1992) Properties of a three-dimensional Poisson-Voronoi tessellation: a Monte Carlo study. Journal of Statistical Physics, 67, 523 – 551.

Meijering, J.L. (1953) Interface area, edge length, and number of vertices in crystal aggregates with random nucleation. Philips Research Reports, 8, 270 – 290.

Tanemura, M. (1988) Random packing and random tessellation in relation to the dimension of space. Journal of Microscopy, 151, 247 – 255.

Tanemura, M., Ogawa, T. and Ogita, N. (1983) A new algorithm for three-dimensional Voronoi tessellation. Journal of Computational Physics, 51, 191 – 207.

 
 
NEXT

HOME