Centroidal Voronoi Tessellations: Algorithms, Applications, and Theory

点击翻译按钮获取中文摘要

A centroidal Voronoi tessellation (CVT) is a Voronoi tessellation of agiven set such that the associated generating points are centers of mass of the corresponding Voronoi regions. Applications of CVT's range from problems in image compression, vector quantization, quadrature rules, grid generation and optimization, finite difference schemes, distribution of resources, cellular biology, cluster analysis, and the territorial behavior of animals. The goals are to develop highlyefficient parallel algorithms for the computation of CVT's, to gain further understanding of interesting features related to the these tessellations, to implement and test these algorithms, and to produce a useful software suite that can serve as a design tool for manyproblems in applications.Among the theoretical questions to be studied are the complexity of algorithms for the construction of CVT's, the effects of nonuniform densities, CVT's in general metrics, constrained CVT's, and generalizedCVT's based on lines, curves and surfaces.Parallel deterministic and probabilistic algorithms will be developed and tested. In the former case, different averaging and communicationstrategies will be examined; for the latter,domain decomposition ideas will be exploited. This effort can lead to parallel grid generation algorithms and other software useful in applications such asclustering analysis.Applications of CVT's will also be studied, with particular emphasis on grid generation and optimization. The questions addressed in thisconnection include the role of the density functions used to generate the CVT's on the optimal placement of grid points, the construction of grids with special properties and the the use of various generalized CVT's. Another application that will be examined are the use of CVT's in the clustering analysis of large data sets.