Voronoi diagrams

Aurenhammer, F. (1991). Voronoi Diagrams - A Survey of Fundamental Geometric Data Structure. ACM Comp.Serv.,23, 345-405. 

We have been using computers in supposedly more sophisticated applications, such as representation of the pair radial distribution function g(R) (29). construction of the Voronoi diagram (30), simulation of light scattering in polymer solutions (31) or Monte Carlo simulation of a fluid with central force fields (32). The present application is anything but sophisticated we... 

The composition mole fractions are nonnegativc and sum to unity, and so the allowed compositions are constrained to lie within a simplex in d -1 dimensions. For the familiar ternary system, this simplex is an equilateral triangle, as shown in Fig. 3b. Typically, several phases will exist for different compositions of the material. The figures of merit will be dramatically different between each of these distinct phases. To mimic this expected behavior, the composition variables are grouped in the random phase volume model into phases centered around Vj points randomly placed within the allowed composition range. The phases form a Voronoi diagram (Sedgewick, 1988), as shown in Fig. 4. 

During the last two decades, skeletonization (i.e. extracting skeleton from digital binary images) has become a challenging research field. Three major skeletonization techniques have been proposed the distance transform method, the method based on Voronoi diagrams and the iterative object reduction method, also called thinning . 

An example of generating of a synthetic collaret topology modeled by a randomly generated curve is shown in Figure 22.10a. Figure 22.10b illustrates three different patterns obtained by this method. Other layer patterns can be generated based on wavelet, Fourier, polar, and distance transforms, as well as Voronoi diagrams [8]. 

Once a pore space is known, a pore network can be created through a variety of methods. Methods that reduce the pore space into a topologically equivalent skeleton involve either a thiiming algorithm or, in the case of the 2D models " -a Voronoi diagram around the material locations. An alternative method to determine the representative pore network for a pore space is the maximal ball method, which is a computationally inexpensive techniqne that has been demonstrated for GDL-like structures. ... 

Figure 7 Voronoi diagram. Each point in the plane is assigned to the dot it lies closest to...

Bhattacharya, R, Gavrilova, M. L. (2008). Roadmap-based path planning - Using the Voronoi diagram for a clearance-based shortest path. IEEE Robotics Automation Magazine, 15, 58-66. doi 10.1109/MRA.2008.921540... 

A. Okabe, B. Boots, K. Sugihara, and S.N. Chiu (2000) Spatial tessellations Concepts and Applications of Voronoi Diagrams. J. Wiley and Sons. Ltd., Chichester. 

We present an approximate algorithm, based on the Voronoi diagram of the terrain, which is a variant of the popular retraction algorithm [14], We then present algorithms that operate on dual graphs... 

The method used to estimate the bound on P is explained as follows. We first choose a shortest path in the original terrain, and then imagine that each obstacle is "expanded" until its boundary touches the Voronoi diagram (but does not cross it). Then we track the expanded version of and obtain an upper bound on the length of this expanded path, which is definitely an upper bound on the path returned by our algorithm. The same method is used in the next section also and the details of the derivation of these bounds will be given in a forthcoming report. 

We can obtain the constrained triangulation based on the Voronoi diagram in 0 n ogn) time [15]. We can also use the other types of decompositions to yield algorithms that are similar to the ones of this section. A survey of algorithms to obtain several types of decompositions can be found in [4]. 

---