Study on Algorithms and Applications of Centroidal Voronoi Tessellations

质心Voronoi曲面细分算法及应用研究

• 批准号: 0913491
• 负责人: Lili Ju
• 金额: $ 18万
• 依托单位: University South Carolina Research Foundation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-09-01 至 2012-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0913491&HistoricalAwards=false
• 关键词: Study; Algorithms; Applications; Centroidal; Voronoi

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.

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