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.

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.

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.

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.

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.

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.

A unified framework for isotropic meshing based on narrowband Euclidean distance transformation

In this paper, we propose a simpleyet-effective method for isotropic meshing relying on Euclidean distance transformation based centroidal Voronoi tessellation(CVT). Our approach improves the performance and robustness of computing CVT on curved domains while simultaneously providing highquality output meshes. While conventional extrinsic methods compute CVTs in the entire volume bounded by the input model, we restrict the computation to a 3D shell of user-controlled thickness. Taking voxels which contain surface samples as sites, we compute the exact Euclidean distance transform on the GPU. Our algorithm is parallel and memory-efficient,and can construct the shell space for resolutions up to 20483 at interactive speed. The 3D centroidal Voronoi tessellation and restricted Voronoi diagrams are also computed efficiently on the GPU. Since the shell space can bridge holes and gaps smaller than a certain tolerance, and tolerate non-manifold edges and degenerate triangles, our algorithm can handle models with such defects, which typically cause conventional remeshing methods to fail. Our method can process implicit surfaces, polyhedral surfaces, and point clouds in a unified framework. Computational results show that our GPU-based isotropic meshing algorithm produces results comparable to state-ofthe-art techniques, but is significantly faster than conventional CPU-based implementations.