Grid generation and optimization based on centroidal Voronoi tessellations

Centroidal Voronoi tessellations (CVTs) are Voronoi tessellations of a region such that the generating points of the tessellations are also the centroids of the corresponding Voronoi regions. Such tessellations are of use in very diverse applications, including data compression, clustering analysis, cell biology, territorial behavior of animals, and optimal allocation of resources. In this paper, we explore the use of CVTs in grid generation in connection with finite element approximations of partial differential equations. We being by describing these tessellations and methods for their determination. We then discuss their application to mesh generation and finish with some examples of their use for the solution of partial differential equations. (C) 2002 Elsevier Science Inc. All rights reserved.