Study on Algorithms and Applications of Centroidal Voronoi Tessellations

这项提案是利用2009年《美国复苏和再投资法案》(公法111-5)提供的资金授予的。质心Voronoi镶嵌(CVT)是一种特殊的Voronoi镶嵌，其性质是Voronoi镶嵌的生成元对于给定的密度函数也是相应的Voronoi网格的质心。在这个项目中，我们将继续研究计算CVT的算法以及基于CVT的科学和工程问题的应用。项目的主题包括：Lloyd算法的单极点收敛分析研究；计算CVT的非线性共轭梯度方法的开发和分析；分布式系统上CVT/CVDT网格并行生成的研究和实现；改进现有的基于CCVT的曲面网格划分技术；将这些网格划分方案融入偏微分方程组的自适应解，特别是对流占优的问题；以及结合图像颜色空间的强度信息和物理空间的局部边缘信息的边缘加权CVT模型和相应的图像分割算法的进一步研究和改进。在过去的十年里，基于CVT的方法已被证明在各种应用中非常有用，包括但不限于图像处理、矢量量化和数据分析、资源优化、用于控制的传感器和执行器的优化布置、细胞生物学和动物的区域行为、高质量的点采样、网格生成和优化、数值偏微分方程组、气候和大气科学、模型简化、计算机图形和视觉、移动传感网络、物流系统设计等。拟议的项目涵盖了CVT的算法设计和分析、实现以及在科学和工程中的各种问题的应用。数学工具被用来分析这些技术，为它们的适用性提供指导；实际考虑包括并行实现问题，以使算法在实际应用和大规模计算中具有竞争力。所提出的研究将为理解优雅的Lloyd算法提供新的见解，也将导致对许多重要应用的转换概念的探索和计算算法的更新，包括网格优化、自适应算法、能量最小化和基于CVT方法的图像处理。此外，该项目还将为对计算和应用数学、工程和信息技术感兴趣的研究生提供一个独特的教育机会，让他们参与一个跨学科的研究计划。

This proposal is awarded using funds made available by the American Recovery and Reinvestment Act of 2009 (Public Law 111-5). Centroidal Voronoi tessellations (CVTs) are special Voronoi tessellations having the propertythat the generators of the Voronoi tessellations are also the centroids, with respect to a given density function, of the corresponding Voronoi cells. In this project, we will continue to investigate algorithms for computing CVTs and CVT-based applications for scientific and engineering problems. Topics of the proposed project include: study of single limit-point convergence analysis for the Lloyd's algorithm; development and analysis of nonlinear conjugate gradient methods for computing CVTs; study and implementation of parallel CVT/CVDT mesh generation on the distributed systems; improving existing CCVT-based techniques for surface meshing; incorporating these meshing schemes in adaptive solutions of partial differential equations, especially for the convection-dominated problems; and further investigation and improvement of the edge-weighted CVT model and corresponding algorithms for image segmentation that combines the intensity information in the color space of the image and the local edge information in the physical space. CVT-based methodologies have been proven to be very useful in diverse applications in the past decade, including but not limited to, image processing, vector quantization and data analysis, resource optimization, optimal placement of sensors and actuators for control, cell biology and territorial behavior of animals, high-quality point sampling, mesh generation and optimization, numerical partial differential equations, climate and atmospheric science, model reduction, computer graphics and vision, mobile sensing networks, logistics system design, and etc. The application list is still growing. The proposed project has a comprehensive coverage of algorithm design and analysis, implementation and applications of CVTs to diverse problems in science and engineering. Mathematical tools are used to analyze these techniques to give guidelines for their applicability; practical considerations including parallel implementation issues are addressed to make the algorithms competitive in real applications and large scale computations. The proposed investigation will offer new insight into the understanding of the elegant Lloyd's algorithm and it will also lead to exploration of transformative concepts and renovation of computational algorithms for many important applications involving mesh optimization, adaptive algorithms, energy minimizationand image processing based on the CVT methodologies. In addition, this project will also offer a unique educational opportunity for graduate students with interests in computational and applied mathematics, engineering and information technology by having them participate in an interdisciplinary research program.