# Computation of Compact Distributions of Discrete Elements
## 2 Related Work
[3] calculated quantities such as the distance, angle, separation, and superposition between all the elements in the sample pattern and calculated their averages, variances, and Gaussian distributions. During synthesis, distributions of the peak points will gradually accord with the statistical features of the sample data via constant iteration. Other researchers, such as [PERSON] [4], calculated the probability density function of elements of all types and synthesized the element distribution based on the calculation results. Some other researchers considered the statistical and local features of the entire set. [PERSON] [1] extended the local neighborhood matching to an overall energy function optimization process, while [PERSON] et al. [5], in addition to proposing a neighborhood coding method to describe the element neighborhood features, considered the overall features, such as the density and minimum distance, of all kinds of elements. Sample-based methods have proven to be efficient in synthesizing discrete elements. However, when elements are closely arranged, a number of problems will occur due to the neglect of collision and overlapping situations between elements. If we take the collision and overlapping situations into consideration, the amount of calculation will be significantly increased. **Process-based modeling. ** In the process-based methods for element distribution simulation, finding the element distributions is regarded as a random sampling or an overall optimization process. Many methods have been adopted to generate different element space distributions, among which the Poisson disk distribution is the most popular. This distribution can ensure that the elements are as evenly arranged as possible, while the distance between any two elements is not less than a user-defined threshold value. The two most classic algorithms to generate Poisson disk distributions are the dart-throwing algorithm [6] and [PERSON] method [14]. [PERSON] method, via progressive optimization in a certain region, constructs the Voronoi diagram to create point distributions. Then, the entire region is partitioned into small regions by every Voronoi region. On this basis, if these polygons have similar shapes to those of the discrete elements, the elements can be closely arranged by simply putting them into these polygons. **Voronoi diagram. ** The Voronoi diagram is a kind of fundamental data structure of space proximity relations [22]. On the basis of point set P of a plane, this diagram can divide this plane into Voronoi regions in the shape of a convex polygon. Every point \(\mathrm{p_{i}}\) in the P corresponds a region \(\mathrm{V_{i}}\), making the distance between any point in \(\mathrm{V_{i}}\) and \(\mathrm{p_{i}}\) shorter than that between any point in \(\mathrm{V_{i}}\) and \(\mathrm{p_{j}}\) (\(j\
eq\)i). When generating the Voronoi diagram, various Voronoi region shapes can be achieved by adopting different distance metrics. Normally, the \(\mathrm{L_{p}}\)-metrics is the most commonly used (also known as Minkowski distance) [23]. When \(\mathrm{p}=2\) (that is, \(\mathrm{L_{2}}\)-metrics), the shapes of Voronoi regions generated will approach a regular hexagon. When \(\mathrm{p}=1\) (also known as Manhattan distance), the shapes will be the square rotated 45 degrees. [PERSON] et al. [14] attempted to adopt this function for compact distribution of square-shaped elements. Apart from \(\mathrm{L_{p}}\)-metrics, other functions like convex polygon-offset distance function [24] and the Moscow metric [25] are also introduced by researchers. There are also related works on the anisotropic Voronoi synthesis [26]. Moreover, the definition of the Voronoi diagram has been extended from two dimensions to three or more dimensions. The Voronoi diagram over curved surfaces [27; 28] has also been researched. Some researchers even conducted work on the Voronoi diagram in non-Euclidean space metrics (like Riemannian geometry metric) [29; 30].