Centroidal Voronoi Tessellations for Mesh Generation

Mesh generation in regions in Euclidean space is a central task in computational science, especially for commonly used numerical methods for the solution of partial differential equations (PDEs), e.g., finite element and finite volume methods. Mesh generation can be classified into several categories depending on the element sizes (uniform or non-uniform) and shapes (isotropic or anisotropic). Uniform meshes have been well studied and still find application in a wide variety of problems. However, when solving certain types of partial differential equations for which the solution variations are large in some regions of the domain, non-uniform meshes result in more efficient calculations. If the solution changes more rapidly in one direction than in others, non-uniform anisotropic meshes are preferred. In this work, first we present an algorithm to construct uniform isotropic meshes and discuss several mesh quality measures. Secondly we construct an adaptive method which produces non-uniform anisotropic meshes that are well suited for numerically solving PDEs such as the convection diffusion equation. For the uniform Delaunay triangulation of planar regions, we focus 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. Furthermore, 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 isotropic grids and that the CVT-based grids are at least as good as any of the others. For more general grid generation settings, e.g., non-uniform and/or anistropic grids, such quantitative comparisons are much more difficult, if not impossible, to either make or interpret. This motivates us to develop CVT-based adaptive non-uniform anisotropic mesh refinement in the context of solving the convection-diffusion equation with emphasis on convection-dominated problems. The challenge in the numerical approximation of this equation is due to large variations in the solution over small regions of the physical domain. Our method not only refines the underlying grid at these regions but also stretches the elements according to the solution variation. Three main ingredients are incorporated to improve the accuracy of numerical solutions and increase the algorithm's robustness and efficiency. First, a streamline upwind Petrov Galerkin method is used to produce a stabilized solution. Second, an adapted metric tensor is computed from the approximate solution. Third, optimized anisotropic meshes are generated from the computed metric tensor. Our algorithm has been tested on a variety of 2-dimensional examples. It is robust in detecting layers and efficient in resolving non-physical oscillations in the numerical approximation.