# Computation of Compact Distributions of Discrete Elements
## 1 Introduction  
The synthesis of texture patterns has been an important research subject. Traditional texture synthesis technologies are mainly designed for raster textures, which record texture information only in the form of raster images and have no explicit records or expressions of the geometric content expressed in the textures (such as basic units composing the textures and unit distribution information). Gradually, a number of texture patterns have been found to be distributions of numerous discrete elements. If images are described as geometric distributions of many vector elements, a better effect of pattern synthesis will be achieved from the aspect of element distribution. On this basis, many researchers have begun studying the topics of discrete element distribution [1; 2; 3; 4; 5; 6; 7; 8; 9], among which the synthesis of compact element distributions is the most challenging. Compact element distributions need to arrange one or several given types of elements in a random and possibly compact way (as show in Figure 1, the compact distribution effects of square and circular elements). This process calls for not only the attention to the element location distributions, but also judgment of the crashing and overlapping relations between elements, which are closely connected with the shapes of the elements. Therefore, it has been a difficult task to synthesize compact element distributions. Currently, the majority of the research is focused on discrete element distributions. Although some researchers, such as [PERSON] [10] and [PERSON] [5], have achieved relatively compact element distributions, their methods require both the construction of complicate relations between elements and algorithms with high computational complexity. Other researchers have studied compact element distributions from the aspect of space division, among which the Voronoi diagram is the most frequently used. The Voronoi diagram is a plane partitioning method based on distance, which can effectively achieve small-region partitioning. Some researchers utilized the Voronoi diagram to partition the space to achieve the compact distribution of small-region elements [11; 12; 13]. Other studies [11; 12; 13] adopted L\({}_{2}\)-metric as a distance measurement, thus making the shape of the small regions defined as approximately hexagonal. [PERSON] et al. [14] tried to use the Manhattan distance to measure the distance in the Voronoi diagram, thereby generating a partition of regions similar to square shapes. However, in the practical application, like mosaic pattern synthesis, compact distributions of elements in various shapes will be frequently needed. Drawing from this, we modify the distance metric to affect the shape of the Voronoi region remarkably, thus generating partition of Voronoi region in various shapes. This paper attempts to adopt four distance metrics to realize several types of region partitions, such as those composed of rectangles, circles, ovals, and triangles, and to further achieve compact element distributions of many shapes. Compared with traditional methods, our method is characterized by the following advantages:  
(1) Compact distributions of elements of various shapes were achieved. By adopting different distance metrics of the Voronoi diagram, the shapes of the generated Voronoi regions can be controlled, thus realizing compact distributions of elements of various shapes, such as rectangles, circles, triangles, and ovals. (2) Our method is highly efficient. By converting the Voronoi generation process into a graphical rendering process, the GPU (Graphics Processing Unit) parallel computing ability can be fully utilized for calculation, and thus the synthesis speed can reach interactive efficiency. (3) The pattern synthesis can be controlled. By adjusting parameters, users are able to control the size and distribution direction of elements and further control the pattern synthesis to satisfy various synthesis requirements.