Abstract. In this paper, we introduce a novel definition of the anisotropic centroidal Voronoi tessellation (ACVT) corresponding to a given Riemann metric tensor. A directional distance function is used in the definition to simplify the computation. We provide algorithms to approximate the ACVT using the Lloyd iteration and the construction of anisotropic Delaunay triangulation under the given Riemannian metric. The ACVT is applied to optimization of two dimensional anisotropic Delaunay triangulation, to the generation of surface CVT and high quality triangular mesh on general surfaces. Various numerical examples demonstrate the effectiveness of the proposed method. Key words. Voronoi tessellations, anisotropy, Riemannian metric, anisotropic Delaunay triangulation, optimal tessellations, optimal mesh, surface mesh, surface triangulation AMS subject classifications. 65D18, 65D17, 65N50, 65Y20 1. Introduction. Anisotropic triangulations, in particular, anisotropic Delaunay triangulations, have attracted the attention of many researchers, see [6, 9, 10, 22, 25, 28, 29] and the references cited therein, due to their various applications ranging from volume and surface mesh generation to surface representation and image morphing. For best-performing triangulations, from the approximation theory point of view, it is well known that the aspect ratios and orientations of the triangles or tetrahedra should depend on the problems whose solutions are to be approximated. For problems such as in fluid flow, the solutions often display anisotropic behavior and are best resolved with anisotropic meshes. Same as in the isotropic case [19] , the quality of the triangulation is closely related to the distribution of the vertices. In [12] , a methodology for optimal points placement in regions, i.e., volumes, in R d has been developed, based on the notion of centroidal Voronoi tessellations (CVTs). A CVT is a Voronoi tessellation whose generating points are the centroids (centers of mass) of the corresponding Voronoi regions associated with a given density. CVT's enjoy an optimization characteristics so that they themselves turn out to be useful in many applications such as image and data analysis, vector quantization, resource optimizations, statistics, and meshless computing; see, e.g., [12, 14, 15] . The concept of CVT has also been successfully applied to high quality mesh generation and optimization [13, 17, 18, 19] , and to numerical solution of partial differential equations. The basic definition of the CVT can be generalized to very broad settings ranging from abstract spaces to discrete point sets [12] . The purpose of this paper is to introduce a new and consistent definition for anisotropic centroidal Voronoi tessellations in the Euclidean space but related to a given Riemannian metric tensor which possesses anisotropy, and to develop computational algorithms for their efficient construction. By introducing a directional distance definition for any two points as a significant simplification of the classical Riemann distance measure, the notion of Anisotropic
Du et al. REF propose a simplification of vector fields resulting in a predefined number of clusters based on Centroidal Voronoi tessellations (CVTs).
Anisotropic centroidal Voronoi tessellations and their applications
SIAM J. Sci. Comput
Mathematics Computer Science