A nearest neighbor sweep circle algorithm for computing discrete Voronoi tessellations

An algorithm for computing discrete, 2-dimensional, Euclidean Voronoi tessellations is presented. The algorithm combines a limiting sweep circle approach with a nearest neighbor cellular approach. It reduces the computational cost of the naïve approach while at the same time giving the Euclidean Voronoi tessellations that simple nearest neighbor algorithms are unable to produce. The algorithm is shown, through analytical methods, to produce good approximations to corresponding continuous Voronoi tessellations depending on the definition of neighbor used in the nearest neighbor step and the mesh size. The quality of different types of neighbor definitions are discussed as well as the computational cost. The algorithm is general enough to be easily extended to higher dimensions and nonuniform meshes. The analysis lays the groundwork for the computation of discrete centroidal Voronoi tessellations where some kind of numerical integration is required.     

2D Centroidal Voronoi Tessellations with Constraints

<正>We tackle the problem of constructing 2D centroidal Voronoi tessellations with constraints through an efficient and robust construction of bounded Voronoi diagrams, the pseudo-dual of the constrained Delaunay triangulation.We exploit the fact that the cells of the bounded Voronoi diagram can be obtained by clipping the ordinary ones against the constrained Delaunay edges.The clipping itself is efficiently computed by identifying for each constrained edge the(connected) set of triangles whose dual Voronoi vertices are hidden by the constraint.The resulting construction is amenable to Lloyd relaxation so as to obtain a centroidal tessellation with constraints.     

Truncated Newton-Based Multigrid Algorithm for Centroidal Voronoi Diagram Calculation

In a variety of modern applications there arises a need to tessellate the domain into representative regions, called Voronoi cells. A particular type of such tessellations, called centroidal Voronoi tessellations or CVTs, are in big demand due to their optimality properties important for many applications. The availability of fast and reliable algorithms for their construction is crucial for their successful use in practical settings. This paper introduces a new multigrid algorithm for constructing CVTs that is based on the MG/Opt algorithm that was originally designed to solve large nonlinear optimization problems. Uniform convergence of the new method and its speedup comparing to existing techniques are demonstrated for linear and nonlinear densities for several 1d and 2d problems, and $O(k)$ complexity estimation is provided for a problem with $k$ generators.     

Three-Dimensional Finite Element Superconvergent Gradient Recovery on Par6 Patterns

<正>In this paper,we present a theoretical analysis for linear finite element superconvergent gradient recovery on Par6 mesh,the dual of which is centroidal Voronoi tessellations with the lowest energy per unit volume and is the congruent cell predicted by the three-dimensional Gersho's conjecture.We show that the linear finite element solution u_h and the linear interpolation u_1 have superclose gradient on Par6 meshes. Consequently,the gradient recovered from the finite element solution by using the superconvergence patch recovery method is superconvergent to▽u.A numerical example is presented to verify the theoretical result.     

Edge-Weighted Centroidal Voronoi Tessellations

<正>Most existing applications of centroidal Voronoi tessellations(CVTs) lack consideration of the length of the cluster boundaries.In this paper we propose a new model and algorithms to produce segmentations which would minimize the total energy—a sum of the classic CVT energy and the weighted length of cluster boundaries.To distinguish it with the classic CVTs,we call it an Edge-Weighted CVT(EWCVT).The concept of EWCVT is expected to build a mathematical base for all CVT related data classifications with requirement of smoothness of the cluster boundaries.The EWCVT method is easy in implementation,fast in computation,and natural for any number of clusters.     

Cooperative Sensing and Distributed Control of a Diffusion Process Using Centroidal Voronoi Tessellations

<正>This paper considers how to use a group of robots to sense and control a diffusion process.The diffusion process is modeled by a partial differential equation (PDE),which is a both spatially and temporally variant system.The robots can serve as mobile sensors,actuators,or both.Centroidal Voronoi Tessellations based coverage control algorithm is proposed for the cooperative sensing task.For the diffusion control problem,this paper considers spraying control via a group of networked mobile robots equipped with chemical neutralizers,known as smart mobile sprayers or actuators,in a domain of interest having static mesh sensor network for concentration sensing.This paper also introduces the information sharing and consensus strategy when using centroidal Voronoi tessellations algorithm to control a diffusion process.The information is shared not only on where to spray but also on how much to spray among the mobile actuators.Benefits from using CVT and information consensus seeking for sensing and control of a diffusion process are demonstrated in simulation results.     

Percolation on random Johnson–Mehl tessellations and related models

We make use of the recent proof that the critical probability for percolation on random Voronoi tessellations is 1/2 to prove the corresponding result for random Johnson–Mehl tessellations, as well as for two-dimensional slices of higher-dimensional Voronoi tessellations. Surprisingly, the proof is a little simpler for these more complicated models. B. Bollobás’s research was supported in part by NSF grants CCR-0225610 and DMS-0505550 and ARO grant W911NF-06-1-0076. O. Riordan’s research was supported by a Royal Society Research Fellowship.     

Bernoulli Cluster Field: Voronoi Tessellations

A new point process is proposed which can be viewed either as a Boolean cluster model with two cluster modes or as a p-thinned Neyman-Scott cluster process with the retention of the original parent point. Voronoi tessellation generated by such a point process has extremely high coefficients of variation of cell volumes as well as of profile areas and lengths in the planar and line induced tessellations. An approximate numerical model of tessellation characteristics is developed for the case of small cluster size; its predictions are compared with the results of computer simulations. Tessellations of this type can be used as models of grain structures in steels.     

Numerical Analysis of the Fracture Toughness of Low-Density Open-Cell Voronoi Foams

Mechanics of Composite Materials - In this study, the geometry of open-cell foams is simulated using a model based on Voronoi tessellations. The fracture toughness of open-cell foams with Voronoi...     

R-Adaptive Reconnection-Based Arbitrary Lagrangian Eulerian Method-R-ReALE

We present a new R-adaptive Arbitrary Lagrangian Eulerian (ALE) method, based on the reconnection-based ALE - ReALE methodology [5, 41, 42]. The main elements in a standard ReALE method are: an explicit Lagrangian phase on an arbitrary polygonal (in 2D) mesh, followed by a rezoning phase in which a new grid is defined, and a remapping phase in which the Lagrangian solution is transferred onto the new grid. The rezoned mesh is smoothed by using one or several steps toward centroidal Voronoi tessellation, but it is not adapted to the solution in any way. We present a new R-adaptive ReALE method (R-ReALE, where R stands for Relocation). The new method is based on the following design principles. First, a monitor function (or error indicator) based on Hessian of some flow parameter(s), is utilized. Second, the new algorithm uses the equidistribution principle with respect to the monitor function as criterion for defining an adaptive mesh. Third, centroidal Voronoi tessellation is used for the construction of the adaptive mesh. Fourth, we modify the raw monitor function (scale it to avoid extremely small and large cells and smooth it to create a smooth mesh), in order to utilize theoretical results related to centroidal Voronoi tessellation. In the R-ReALE method, the number of mesh cells is chosen at the beginning of the calculation and does not change with time, but the mesh is adapted according to the modified monitor function during the rezone stage at each time step. We present all details required for implementation of the new adaptive R-ReALE method and demonstrate its performance relative to standard ReALE method on a series of numerical examples.     

Simulation of typical Cox–Voronoi cells with a special regard to implementation tests

We consider stationary Poisson line processes in the Euclidean plane and analyze properties of Voronoi tessellations induced by Poisson point processes on these lines. In particular, we describe and test an algorithm for the simulation of typical cells of this class of Cox–Voronoi tessellations. Using random testing, we validate our algorithm by comparing theoretical values of functionals of the zero cell to simulated values obtained by our algorithm. Finally, we analyze geometric properties of the typical Cox–Voronoi cell and compare them to properties of the typical cell of other well-known classes of tessellations, especially Poisson–Voronoi tessellations. Our results can be applied to stochastic–geometric modelling of networks in telecommunication and life sciences, for example. The lines can then represent roads in urban road systems, blood arteries or filament structures in biological tissues or cells, while the points can be locations of telecommunication equipment or vesicles, respectively.     

Asymptotics for Statistical Distances Based on Voronoi Tessellations

We obtain an information-type inequality and a strong law for a wide class of statistical distances between empirical estimates and random measures based on Voronoi tessellations. This extends some basic results in the asymptotic theory of sample spacings, when the cells of the Voronoi tessellation are interpreted as d-dimensional spacings.     

Poisson polyhedra in high dimensions

The zero cell of a parametric class of random hyperplane tessellations depending on a distance exponent and an intensity parameter is investigated, as the space dimension tends to infinity. The model includes the zero cell of stationary and isotropic Poisson hyperplane tessellations as well as the typical cell of a stationary Poisson Voronoi tessellation as special cases. It is shown that asymptotically in the space dimension, with overwhelming probability these cells satisfy the hyperplane conjecture, if the distance exponent and the intensity parameter are suitably chosen dimension-dependent functions. Also the high dimensional limits of the mean number of faces are explored and the asymptotic behaviour of an isoperimetric ratio is analysed. In the background are new identities linking the f-vector of the zero cell to certain dual intrinsic volumes.     

Analysis of a Class of Symmetric Equilibrium Configurations for a Territorial Model

<正>Motivated by an animal territoriality model,we consider a centroidal Voronoi tessellation algorithm from a dynamical systems perspective.In doing so,we discuss the stability of an aligned equilibrium configuration for a rectangular domain that exhibits interesting symmetry properties.We also demonstrate the procedure for performing a center manifold reduction on the system to extract a set of coordinates which capture the long term dynamics when the system is close to a bifurcation.Bifurcations of the system restricted to the center manifold are then classified and compared to numerical results.Although we analyze a specific set-up,these methods can in principle be applied to any bifurcation point of any equilibrium for any domain.     

Periodic three-dimensional mesh-generation for Voronoi tessellations with application to cubic crystal aggregates

We present a technique for the generation of unstructured periodic spatial discretizations of three–dimensional Voronoi tessellations. These define model microstructures for various polycrystalline aggregates. The elastic properties of cubic crystal aggregates are examined numerically using periodic displacement boundary conditions. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

The Poisson Voronoi Tessellation II. Edge Length Distribution Functions

This paper presents a method for the determination of the distribution function of the length of the 'typical' edge of the Poisson Voronoi tessellation. The method is based on distributional properties of the configuration of the centres in the neighbourhood of the 'typical' vertex. The distribution and density functions of the edge lengths are given in double integral form for various dimensions. Analogous characteristics are considered for two-dimensional sections through higher-dimensional Poisson Voronoi tessellations.     

Simulation Studies of Some Voronoi Point Processes

We introduce a new class of dynamic point process models with simple and intuitive dynamics that are based on the Voronoi tessellations generated by the processes. Under broad conditions, these processes prove to be ergodic and produce, on stabilisation, a wide range of clustering patterns. In the paper, we present results of simulation studies of three statistical measures (Thiel’s redundancy, van Lieshout and Baddeley’s J-function and the empirical distribution of the Voronoi nearest neighbours’ numbers) for inference on these models from the clustering behaviour in the stationary regime. In particular, we make comparisons with the area-interaction processes of Baddeley and van Lieshout.     

Advances in Studies and Applications of Centroidal Voronoi Tessellations

<正>Centroidal Voronoi tessellations(CVTs) have become a useful tool in many applications ranging from geometric modeling,image and data analysis,and numerical partial differential equations,to problems in physics,astrophysics,chemistry,and biology. In this paper,we briefly review the CVT concept and a few of its generalizations and well-known properties.We then present an overview of recent advances in both mathematical and computational studies and in practical applications of CVTs.Whenever possible,we point out some outstanding issues that still need investigating.     

Constrained CVT meshes and a comparison of triangular mesh generators

Mesh generation in regions in Euclidean space is a central task in computational science, and especially for commonly used numerical methods for the solution of partial differential equations, e.g., finite element and finite volume methods. We focus on the uniform Delaunay triangulation of planar regions and, in particular, on how one selects the positions of the vertices of the triangulation. We discuss a recently developed method, based on the centroidal Voronoi tessellation (CVT) concept, for effecting such triangulations and present two algorithms, including one new one, for CVT-based grid generation. We also compare several methods, including CVT-based methods, for triangulating planar domains. To this end, we define several quantitative measures of the quality of uniform grids. We then generate triangulations of several planar regions, including some having complexities that are representative of what one may encounter in practice. We subject the resulting grids to visual and quantitative comparisons and conclude that all the methods considered produce high-quality uniform grids and that the CVT-based grids are at least as good as any of the others.     

Coupled Models and Parallel Simulations for Three-Dimensional Full-Stokes Ice Sheet Modeling

A three-dimensional full-Stokes computational model is considered for determining the dynamics,temperature,and thickness of ice sheets.The goveming thermomechanical equations consist of the three-dimensional full-Stokes system with nonlinear rheology for the momentum,an advective-diffusion energy equation for temperature evolution,and a mass conservation equation for ice-thickness changes.Here,we discuss the variable resolution meshes,the finite element discretizations,and the parallel algorithms employed by the model components.The solvers are integrated through a well-designed coupler for the exchange of parametric data between components.The discretization utilizes high-quality,variable-resolution centroidal Voronoi Delaunay triangulation meshing and existing parallel solvers.We demonstrate the gridding technology,discretization schemes,and the efficiency and scalability of the parallel solvers through computational experiments using both simplified geometries arising from benchmark test problems and a realistic Greenland ice sheet geometry.