Study on Algorithms and Applications of Centroidal Voronoi Tessellations

本提案使用2009年美国复苏和再投资法案（公法111-5）提供的资金进行奖励。质心Voronoi镶嵌（cvt）是一种特殊的Voronoi镶嵌，其性质是Voronoi镶嵌的生成器也是相应Voronoi细胞的给定密度函数的质心。在这个项目中，我们将继续研究计算cvt的算法以及基于cvt的科学和工程问题的应用。拟进行的课题包括：劳埃德算法的单极限点收敛分析研究；非线性共轭梯度法的发展与分析；分布式系统上CVT/CVDT并行网格生成的研究与实现改进现有的基于ccvt的曲面网格划分技术；将这些网格格式应用于偏微分方程的自适应解中，特别是对流主导问题；进一步研究和改进将图像色彩空间中的强度信息与物理空间中的局部边缘信息相结合的边缘加权CVT模型及相应的图像分割算法。在过去的十年中，基于cvt的方法已被证明在各种应用中非常有用，包括但不限于，图像处理，矢量量化和数据分析，资源优化，传感器和执行器的优化放置控制，细胞生物学和动物的领土行为，高质量点采样，网格生成和优化，数值偏微分方程，气候和大气科学，模型简化，计算机图形与视觉、移动传感网络、物流系统设计等。申请名单仍在增长。本项目涵盖了cvt的算法设计和分析、实现以及在科学和工程中各种问题的应用。使用数学工具对这些技术进行分析，为其适用性提供指导；为了使算法在实际应用和大规模计算中具有竞争力，本文还讨论了包括并行实现问题在内的实际考虑。所提出的研究将为理解优雅的劳埃德算法提供新的见解，并且还将导致探索涉及网格优化、自适应算法、能量最小化和基于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.