OF HIGHER DIMENSIONS
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
Fields of interest: Geometry, spatial statistics,
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.
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
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).
f(x|a, b, c) = (abc/a/G(c/a) )xc-1exp(-bxa) (a, b, c > 0) (1)
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
Fig.1 : Observed histograms of the volume of Poisson Voronoi cells
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.