Centroidal Voronoi Tessellations: Algorithms, Applications, and Theory

质心Voronoi曲面细分（CVT）是给定集合的Voronoi曲面细分，使得相关联的生成点是对应的Voronoi区域的质心。CVT的应用范围从图像压缩、矢量量化、求积规则、网格生成和优化、有限差分格式、资源分配、细胞生物学、聚类分析和动物的领土行为等问题。目标是开发用于CVT的计算的高效并行算法，以获得与这些镶嵌相关的有趣特征的进一步理解，实现和测试这些算法，并产生有用的软件套件，可以作为许多应用问题的设计工具。非均匀密度的影响，CVT的一般度量，约束CVT的，和generalizedCVT的基于线，曲线和曲面。并行确定性和概率算法将被开发和测试。在前一种情况下，不同的平均和communicationstrategies将被检查;对于后者，域分解的想法将被利用。这项工作可以导致并行网格生成算法和其他软件的应用，如clustering analysis. CVT的应用也将进行研究，特别强调网格生成和优化。在这方面解决的问题包括用于生成CVT的密度函数在网格点的最佳布置上的作用，具有特殊性质的网格的构造以及各种广义CVT的使用。另一个应用程序，将审查使用CVT的聚类分析的大型数据集。

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.