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.

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.

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.

Reactor field reconstruction from sparse and movable sensors using Voronoi tessellation-assisted convolutional neural networks

The aging of operational reactors leads to increased mechanical vibrations in the reactor interior.The vibration of the incore sensors near their nominal locations is a new problem for neutronic field reconstruction.Current field-reconstruction methods fail to handle spatially moving sensors.In this study,we propose a Voronoi tessellation technique in combination with convolutional neural networks to handle this challenge.Observations from movable in-core sensors were projected onto the same global field structure using Voronoi tessellation,holding the magnitude and location information of the sensors.General convolutional neural networks were used to learn maps from observations to the global field.The proposed method reconstructed multi-physics fields(including fast flux,thermal flux,and power rate)using observations from a single field(such as thermal flux).Numerical tests based on the IAEA benchmark demonstrated the potential of the proposed method in practical engineering applications,particularly within an amplitude of 5 cm around the nominal locations,which led to average relative errors below 5% and 10% in the L_(2) and L_(∞)norms,respectively.

Investigation of stress-induced progressive failure of mine pillars using a Voronoi grain-based breakable block model

The Voronoi grain-based breakable block model(VGBBM)based on the combined finite-discrete element method(FDEM)was proposed to explicitly characterize the failure mechanism and predict the deformation behavior of hard-rock mine pillars.The influence of the microscopic parameters on the macroscopic mechanical behavior was investigated using laboratory-scale models.The field-scale pillar models(width-to-height,W/H=1,2 and 3)were calibrated based on the empirically predicted stress-strain curves of Creighton mine pillars.The results indicated that as the W/H ratios increased,the VGBBM effectively predicted the transition from strain-softening to pseudo-ductile behavior in pillars,and explicitly captured the separated rock slabs and the V-shaped damage zones on both sides of pillars and conjugate shear bands in core zones of pillars.The volumetric strain field revealed significant compressional deformation in core zones of pillars.While the peak strains of W/H=1 and 2 pillars were relatively consistent,there were significant differences in the strain energy storage and release mechanism.W/H was the primary factor influencing the deformation and strain energy in the pillar core.The friction coefficient of the structural plane was also an important factor affecting the pillar strength and the weakest discontinuity angle.The fracture surface was controlled by the discontinuity angle and the friction coefficient.This study demonstrated the capability of the VGBBM in predicting the strengths and deformation behavior of hard-rock pillars in deep mine design.

A typhoon-induced storm surge numerical model with GPU acceleration based on an unstructured spherical centroidal Voronoi tessellation grid

Storm surge is often the marine disaster that poses the greatest threat to life and property in coastal areas.Accurate and timely issuance of storm surge warnings to take appropriate countermeasures is an important means to reduce storm surge-related losses.Storm surge numerical models are important for storm surge forecasting.To further improve the performance of the storm surge forecast models,we developed a numerical storm surge forecast model based on an unstructured spherical centroidal Voronoi tessellation(SCVT)grid.The model is based on shallow water equations in vector-invariant form,and is discretized by Arakawa C grid.The SCVT grid can not only better describe the coastline information but also avoid rigid transitions,and it has a better global consistency by generating high-resolution grids in the key areas through transition refinement.In addition,the simulation speed of the model is accelerated by using the openACC-based GPU acceleration technology to meet the timeliness requirements of operational ensemble forecast.It only takes 37 s to simulate a day in the coastal waters of China.The newly developed storm surge model was applied to simulate typhoon-induced storm surges in the coastal waters of China.The hindcast experiments on the selected representative typhoon-induced storm surge processes indicate that the model can reasonably simulate the distribution characteristics of storm surges.The simulated maximum storm surges and their occurrence times are consistent with the observed data at the representative tide gauge stations,and the mean absolute errors are 3.5 cm and 0.6 h respectively,showing high accuracy and application prospects.

Adaptive triangular mesh coarsening with centroidal Voronoi tessellations

We present a novel algorithm for adaptive triangular mesh coarsening. The algorithm has two stages. First, the input triangular mesh is refined by iteratively applying the adaptive subdivision operator that performs a so-called red-green split. Second, the refined mesh is simplified by a clustering algorithm based on centroidal Voronoi tessellations (CVTs). The accuracy and good quality of the output triangular mesh are achieved by combining adaptive subdivision and the CVTs technique. Test results showed the mesh coarsening scheme to be robust and effective. Examples are shown that validate the method.

Convergent Adaptive Finite Element Method Based on Centroidal Voronoi Tessellations and Superconvergence

We present a novel adaptive finite element method(AFEM)for elliptic equations which is based upon the Centroidal Voronoi Tessellation(CVT)and superconvergent gradient recovery.The constructions of CVT and its dual Centroidal Voronoi Delaunay Triangulation(CVDT)are facilitated by a localized Lloyd iteration to produce almost equilateral two dimensional meshes.Working with finite element solutions on such high quality triangulations,superconvergent recovery methods become particularly effective so that asymptotically exact a posteriori error estimations can be obtained.Through a seamless integration of these techniques,a convergent adaptive procedure is developed.As demonstrated by the numerical examples,the new AFEM is capable of solving a variety of model problems and has great potential in practical applications.

On the calibration and verification of Voronoi-based discontinuous deformation analysis for modeling rock fracture

Since its introduction,discontinuous deformation analysis(DDA)has been widely used in different areas of rock mechanics.By dividing large blocks into subblocks and introducing artificial joints,DDA can be applied to rock fracture simulation.However,parameter calibration,a fundamental issue in discontinuum methods,has not received enough attention in DDA.In this study,the parameter calibration of DDA for intact rock is carefully studied.To this end,a subblock DDA with Voronoi tessellation is presented first.Then,a modified contact constitutive law is introduced,in which the tensile and shear meso-strengths are modified to be independent of the bond lengths.This improvement can prevent the unjustified preferential failure of short edges.A method for imposing confining pressure is also introduced.Thereafter,sensitivity analysis is performed to investigate the influence of the calculated parameters and meso-parameters on the mechanical properties of modeled rock.Based on the sensitivity analysis,a unified calibration procedure is suggested for both cases with and without confining pressure.Finally,the calibration procedure is applied to two examples,including a biaxial compression test.The results show that the proposed Voronoi-based DDA can simulate rock fracture with and without confining pressure very well after careful parameter calibration.

3D random Voronoi grain-based models for simulation of brittle rock damage and fabric-guided micro-fracturing

A grain-based distinct element model featuring three-dimensional （3D） Voronoi tessellations （randompoly-crystals） is proposed for simulation of crack damage development in brittle rocks. The grainboundaries in poly-crystal structure produced by Voronoi tessellations can represent flaws in intact rockand allow for numerical replication of crack damage progression through initiation and propagation ofmicro-fractures along grain boundaries. The Voronoi modelling scheme has been used widely in the pastfor brittle fracture simulation of rock materials. However the difficulty of generating 3D Voronoi modelshas limited its application to two-dimensional （2D） codes. The proposed approach is implemented inNeper, an open-source engine for generation of 3D Voronoi grains, to generate block geometry files thatcan be read directly into 3DEC. A series of Unconfined Compressive Strength （UCS） tests are simulated in3DEC to verify the proposed methodology for 3D simulation of brittle fractures and to investigate therelationship between each micro-parameter and the model＇s macro-response. The possibility of numericalreplication of the classical U-shape strength curve for anisotropic rocks is also investigated innumerical UCS tests by using complex-shaped （elongated） grains that are cemented to one another alongtheir adjoining sides. A micro-parameter calibration procedure is established for 3D Voronoi models foraccurate replication of the mechanical behaviour of isotropic and anisotropic （containing a fabric） rocks. 2014 Institute of Rock and Soil Mechanics, Chinese Academy of Sciences. Production and hosting byElsevier B.V. All rights reserved.

Voronoi Based Discrete Least Squares Meshless Method for Heat Conduction Simulation in Highly Irregular Geometries

A new technique is used in Discrete Least Square Meshfree（DLSM） method to remove the common existing deficiencies of meshfree methods in handling of the problems containing cracks or concave boundaries. An enhanced Discrete Least Squares Meshless method named as VDLSM（Voronoi based Discrete Least Squares Meshless） is developed in order to solve the steady-state heat conduction problem in irregular solid domains including concave boundaries or cracks. Existing meshless methods cannot estimate precisely the required unknowns in the vicinity of the above mentioned boundaries. Conducted researches are limited to domains with regular convex boundaries. To this end, the advantages of the Voronoi tessellation algorithm are implemented. The support domains of the sampling points are determined using a Voronoi tessellation algorithm. For the weight functions, a cubic spline polynomial is used based on a normalized distance variable which can provide a high degree of smoothness near those mentioned above discontinuities. Finally, Moving Least Squares（MLS） shape functions are constructed using a varitional method. This straight-forward scheme can properly estimate the unknowns（in this particular study, the temperatures at the nodal points） near and on the crack faces, crack tip or concave boundaries without need to extra backward corrective procedures, i.e. the iterative calculations for modifying the shape functions of the nodes located near or on these types of the complex boundaries. The accuracy and efficiency of the presented method are investigated by analyzing four particular examples. Obtained results from VDLSM are compared with the available analytical results or with the results of the well-known Finite Elements Method（FEM） when an analytical solution is not available. By comparisons, it is revealed that the proposed technique gives high accuracy for the solution of the steady-state heat conduction problems within cracked domains or domains with concave boundaries and at the same time possesses a high convergence rate which its accuracy is not sensitive to the arrangement of the nodal points. The novelty of this paper is the use of Voronoi concept in determining the weight functions used in the formulation of the MLS type shape functions.

Efficient Generation of Conforming Voronoi Polygonal Surface Mesh

A novel construction algorithm is presented to generate a conforming Voronoi mesh for any planar straight line graph (PSLG). It is also extended to tesselate multiple-intersected PSLGs. All the algorithms are guaranteed to converge. Examples are given to illustrate its efficiency.

Role of grain boundary networks in vortex motion in superconducting films

We study the vortex dynamics of the polycrystalline superconductors in the presence of both random point defects and the generated grain boundary(GB) networks with Voronoi diagram. The synergistic effect of adjacent GBs on restricting the vortex motion in intragranular region is proposed and the corresponding intensity factor of the synergistic effect which characterizes the strength of the synergistic restriction of adjacent grain boundaries is also determined in the present work.The interconnected GBs offer easy-flow channels for vortices in addition to pinning effects on the vortices. The combined channels and the vortex flow patterns in the superconducting film are analyzed in detail from molecular dynamics simulations. Furthermore, it is discovered that the critical current increases with the decrease of magnetic field intensity,temperature, and the average grain size. The large number of vortices results in the enhanced repulsive interaction forcing the vortices to move out from the GBs. The thermal depinning from GBs leads to the lower Lorentz force range. The increase of the grain size causes the number of GBs to decrease. In summary, these effects leads the critical current to become a decreasing function of magnetic field, temperature, and grain size.

An Improved Cooperative Team Spraying Control of a Diffusion Process With a Moving or Static Pollution Source

This paper is concerned with a control problem of a diffusion process with the help of static mesh sensor networks in a certain region of interest and a team of networked mobile actuators carrying chemical neutralizers.The major contribution of this paper can be divided into three parts:the first is the construction of a cyber-physical system framework based on centroidal Voronoi tessellations(CVTs),the second is the convergence analysis of the actuators location,and the last is a novel proportional integral(PI)control method for actuator motion planning and neutralizing control(e.g.,spraying)of a diffusion process with a moving or static pollution source,which is more effective than a proportional(P)control method.An optimal spraying control cost function is constructed.Then,the minimization problem of the spraying amount is addressed.Moreover,a new CVT algorithm based on the novel PI control method,henceforth called PI-CVT algorithm,is introduced together with the convergence analysis of the actuators location via a PI control law.Finally,a modified simulation platform called diffusion-mobile-actuators-sensors-2-dimension-proportional integral derivative(Diff-MAS2D-PID)is illustrated.In addition,a numerical simulation example for the diffusion process is presented to verify the effectiveness of our proposed controllers.

Fast Multilevel CVT-Based Adaptive Data Visualization Algorithm

Efficient data visualization techniques are critical for many scientific applications. Centroidal Voronoi tessellation(CVT) based algorithms offer a convenient vehicle for performing image analysis,segmentation and compression while allowing to optimize retained image quality with respect to a given metric.In experimental science with data counts following Poisson distributions,several CVT-based data tessellation algorithms have been recently developed.Although they surpass their predecessors in robustness and quality of reconstructed data,time consumption remains to be an issue due to heavy utilization of the slowly converging Lloyd iteration.This paper discusses one possible approach to accelerating data visualization algorithms.It relies on a multidimensional generalization of the optimization based multilevel algorithm for the numerical computation of the CVTs introduced in[1],where a rigorous proof of its uniform convergence has been presented in 1-dimensional setting.The multidimensional implementation employs barycentric coordinate based interpolation and maximal independent set coarsening procedures.It is shown that when coupled with bin accretion algorithm accounting for the discrete nature of the data,the algorithm outperforms Lloyd-based schemes and preserves uniform convergence with respect to the problem size.Although numerical demonstrations provided are limited to spectroscopy data analysis,the method has a context-independent setup and can potentially deliver significant speedup to other scientific and engineering applications.

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 uh and the linear interpolation uI 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 Vu. A numerical example is presented to verify the theoretical result.

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.

LED Adaptive Deployment Optimization in Indoor VLC Networks

Driven by the continuous penetration of high data rate services and applications,a large amount of unregulated visible light spectrum is used for communication to fully meet the needs of 6th generation(6G)mobile technologies.Visible light communication(VLC)faces many challenges as a solution that complements existing radio frequency(RF)networks.This paper studies the optimal configuration of LEDs in indoor environments under the constraints of illumination and quality of experience(QoE).Based on the Voronoi tessellation(VT)and centroidal Voronoi tessellation(CVT)theory,combined with the Lloyd’s algorithm,we propose two approaches for optimizing LED deployments to meet the illumination and QoE requirements of all users.Focusing on(i)the minimization of the number of LEDs to be installed in order to meet illumination and average QoE constraints,and(ii)the maximization of the average QoE of users to be served with a fixed number of LEDs.Monte Carlo simulations are carried out for different user distribution compared with hexagonal,square and VT deployment.The simulation results illustrate that under the same conditions,the proposed deployment approach can provide less LEDs and achieve better QoE performance.

An accelerated scheme with high quality mesh based on Lloyd iteration

High quality mesh plays an important role for finite element methods in science computation and numerical simulation.Whether the mesh quality is good or not,to some extent,it determines the calculation results of the accuracy and efficiency.Different from classic Lloyd iteration algorithm which is convergent slowly,a novel accelerated scheme was presented,which consists of two core parts:mesh points replacement and local edges Delaunay swapping.By using it,almost all the equilateral triangular meshes can be generated based on centroidal Voronoi tessellation(CVT).Numerical tests show that it is significantly effective with time consuming decreasing by 40%.Compared with other two types of regular mesh generation methods,CVT mesh demonstrates that higher geometric average quality increases over 0.99.