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.     

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.     

Approximations of a Ginzburg-Landau model for superconducting hollow spheres based on spherical centroidal Voronoi tessellations

In this paper the numerical approximations of the Ginzburg- Landau model for a superconducting hollow spheres are constructed using a gauge invariant discretization on spherical centroidal Voronoi tessellations. A reduced model equation is used on the surface of the sphere which is valid in the thin spherical shell limit. We present the numerical algorithms and their theoretical convergence as well as interesting numerical results on the vortex configurations. Properties of the spherical centroidal Voronoi tessellations are also utilized to provide a high resolution scheme for computing the supercurrent and the induced magnetic field.

     

Aspects of the Facet-Edge Data Structure for the Construction of Voronoi Cells

The construction of Voronoi diagrams has two main aspects: The construction algorithm and the data structure. For the construction of planar Voronoi diagrams e.g. the well known plane sweep algorithm can be applied. Another efficient method is the incremental construction of the Delaunay triangulation by using the quad-edge data structure. Within this data structure the Delaunay triangulation is treated as a planar graph. Incremental construction implies that manipulations of the triangulation are allowed. Its Voronoi diagram is obtained simply by accessing the triangulation's dual graph. We extend this method to tree dimensions, by implementing a 3D Delaunay triangulation on the facet-edge data structure. (© 2010 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

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.     

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.     

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.     

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.     

Farthest-polygon Voronoi diagrams

Given a family of k disjoint connected polygonal sites in general position and of total complexity n, we consider the farthest-site Voronoi diagram of these sites, where the distance to a site is the distance to a closest point on it. We show that the complexity of this diagram is O(n), and give an O(nlog³n) time algorithm to compute it. We also prove a number of structural properties of this diagram. In particular, a Voronoi region may consist of k−1 connected components, but if one component is bounded, then it is equal to the entire region.     

A Fast Robust Algorithm for Computing Discrete Voronoi Diagrams

We describe an algorithm for the construction of discretized Voronoi diagrams on a CPU within the context of a large scale numerical fluid simulation. The Discrete Voronoi Chain (DVC) algorithm is fast, flexible and robust. The algorithm stores the Voronoi diagram on a grid or lattice that may be structured or unstructured. The Voronoi diagram is computed by alternatively updating two lists of grid cells per particle to propagate a growth boundary of cells from the particle locations. Distance tests only occur when growth boundaries from different particles collide with each other, hence the number of distance tests is effectively minimized. We give some empirical results for two and three dimensions. The method generalizes to any dimension in a straight forward manner. The distance tests can be based any metric.     

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.     

Delaunay configurations and multivariate splines: A generalization of a result of B. N. Delaunay

In the 1920s, B. N. Delaunay proved that the dual graph of the Voronoi diagram of a discrete set of points in a Euclidean space gives rise to a collection of simplices, whose circumspheres contain no points from this set in their interior. Such Delaunay simplices tessellate the convex hull of these points. An equivalent formulation of this property is that the characteristic functions of the Delaunay simplices form a partition of unity. In the paper this result is generalized to the so-called Delaunay configurations. These are defined by considering all simplices for which the interiors of their circumspheres contain a fixed number of points from the given set, in contrast to the Delaunay simplices, whose circumspheres are empty. It is proved that every family of Delaunay configurations generates a partition of unity, formed by the so-called simplex splines. These are compactly supported piecewise polynomial functions which are multivariate analogs of the well-known univariate B-splines. It is also shown that the linear span of the simplex splines contains all algebraic polynomials of degree not exceeding the degree of the splines.

     

Delaunay triangulation and 3D adaptive mesh generation

Delaunay triangulation and its complementary structure the Voronoi polyhedra form two of the most fundamental constructs of computational geometry. Delaunay triangulation offers an efficient method for generating high-quality triangulations. However, the generation of Delaunay triangulations in 3D with Watson's algorithm, leads to the appearance of silver tetrahedra, in a relatively large percentage. A different method for generating high-quality tetrahedralizations, based on Delaunay triangulation and not presenting the problem of sliver tetrahedra, is presented. The method consists in a tetrahedra division procedure and an efficient method for optimizing tetrahedral meshes, based on the application of a set of topological Delaunay transformations for tetrahedra and a technique for node repositioning. The method is robust and can be applied to arbitrary unstructured tetrahedral meshes, having as a result the generation of high-quality adaptive meshes with varying density, totally eliminating the appearance of sliver elements. In this way it offers a convenient and highly flexible algorithm for implementation in a general purpose 3D adaptive finite element analysis system. Applications to various engineering problems are presented     

Randomized incremental construction of simple abstract Voronoi diagrams in 3-space

We introduce the simple abstract Voronoi diagram in 3-space as an abstraction of the usual Voronoi diagram. We show that the 3-dimensional simple abstract Voronoi diagram of n sites can be computed in O(n²) expected time using O(n²) expected space by a randomized algorithm. The algorithm is based on the randomized incremental construction technique of Clarkson and Shor (1989). We apply the algorithm to some concrete types of such diagrams: power diagrams, diagrams under ellipsoid convex distance functions, and diagrams under the Hausdorff distance for sites that are parallel segments all having the same length.     

Boundary conforming Delaunay mesh generation

A boundary conforming Delaunay mesh is a partitioning of a polyhedral domain into Delaunay simplices such that all boundary simplices satisfy the generalized Gabriel property. It’s dual is a Voronoi partition of the same domain which is preferable for Voronoi-box based finite volume schemes. For arbitrary 2D polygonal regions, such meshes can be generated in optimal time and size. For arbitrary 3D polyhedral domains, however, this problem remains a challenge. The main contribution of this paper is to show that boundary conforming Delaunay meshes for 3D polyhedral domains can be generated efficiently when the smallest input angle of the domain is bounded by arccos 1/3 ≈ 70.53°. In addition, well-shaped tetrahedra and an appropriate mesh size can be obtained. Our new results are achieved by reanalyzing a classical Delaunay refinement algorithm. Note that our theoretical guarantee on the input angle (70.53°) is still too strong for many practical situations. We further discuss variants of the algorithm to relax the input angle restriction and to improve the mesh quality.     

Computing Voronoi skeletons of a 3-D polyhedron by space subdivision

We tackle the problem of computing the Voronoi diagram of a 3-D polyhedron whose faces are planar. The main difficulty with the computation is that the diagram's edges and vertices are of relatively high algebraic degrees. As a result, previous approaches to the problem have been non-robust, difficult to implement, or not provenly correct.

We introduce three new proximity skeletons related to the Voronoi diagram: (1) the Voronoi graph (VG), which contains the complete symbolic information of the Voronoi diagram without containing any geometry; (2) the approximate Voronoi graph (AVG), which deals with degenerate diagrams by collapsing sub-graphs of the VG into single nodes; and (3) the proximity structure diagram (PSD), which enhances the VG with a geometric approximation of Voronoi elements to any desired accuracy. The new skeletons are important for both theoretical and practical reasons. Many applications that extract the proximity information of the object from its Voronoi diagram can use the Voronoi graphs or the proximity structure diagram instead. In addition, the skeletons can be used as initial structures for a robust and efficient global or local computation of the Voronoi diagram.

We present a space subdivision algorithm to construct the new skeletons, having three main advantages. First, it solves at most uni-variate quartic polynomials. This stands in sharp contrast to previous approaches, which require the solution of a non-linear tri-variate system of equations. Second, the algorithm enables purely local computation of the skeletons in any limited region of interest. Third, the algorithm is simple to implement.     

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.