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网格是一种特殊的Voronoi网格，它的生成元也是对应于给定密度函数的Voronoi单元的质心。在这个项目中，我们将继续研究计算CVT的算法和基于CVT的科学和工程问题的应用。研究内容包括：Lloyd算法的单极限点收敛性分析;非线性共轭梯度法的发展和分析;分布式系统上并行CVT/CVDT网格生成的研究和实现;现有基于CCVT的曲面网格划分技术的改进;将这些网格格式应用于偏微分方程的自适应求解，特别是对流占优问题;并进一步研究和改进了边缘加权CVT模型及相应的图像分割算法，该模型结合了图像颜色空间中的灰度信息和物理空间中的局部边缘信息。在过去的十年中，基于CVT的方法已经被证明在各种应用中非常有用，包括但不限于图像处理、矢量量化和数据分析、资源优化、用于控制的传感器和致动器的最佳放置、细胞生物学和动物的领土行为、高质量点采样、网格生成和优化、数值偏微分方程、气候和大气科学、模型简化、计算机图形和视觉、移动的传感网络、物流系统设计等。拟议的项目有一个全面的覆盖算法设计和分析，实现和应用的CVT在科学和工程中的各种问题。数学工具被用来分析这些技术，给他们的适用性的指导方针，实际的考虑，包括并行实现问题的解决，使算法在真实的应用和大规模计算的竞争力。拟议的调查将提供新的见解优雅的劳埃德算法的理解，它也将导致探索变革的概念和革新的计算算法的许多重要的应用，涉及网格优化，自适应算法，能源minimizationand图像处理的基础上的CVT方法。此外，该项目还将为对计算和应用数学，工程和信息技术感兴趣的研究生提供一个独特的教育机会，让他们参加跨学科的研究计划。