带容积约束Voronoi图的理论和应用研究

本项目研究带容积约束Voronoi图（Capacity-constrained Voronoi Diagram，简称CcVD）的性质、快速计算方法和应用。首先给出CcVD在简单平面区域上的存在条件，并推广到三维区域和空间曲面上。研究连续空间上CcVD目标函数的连续性，并给出梯度的显式计算公式，利用拟牛顿方法快速优化目标函数计算CcVD。针对CcVD目标函数的特点，设计高效的全局优化算法。初步实验结果表明我们计算CcVD的方法比现有方法快了两个数量级。在CcVD的应用方面，着重研究蓝噪声采样问题。结合中心Voronoi图方法，设计新的目标函数，通过优化方法得到高质量的蓝噪声采样结果。在统一的优化框架下，处理平面区域、三维区域、空间曲面等不同区域上的蓝噪声采样问题，以及动态区域和多类（Multi-Class）蓝噪声采样问题。现有文献中还没有一种采样方法能同时处理这些采样问题。

本项目主要研究带容积约束Voronoi图（Capacity-constrained Voronoi Diagram，简称CcVD）的性质、快速计算方法和应用。我们利用变分的思想计算CcVD，给出了CcVD目标函数的梯度计算公式，并采用L-BGFS方法进行快速优化。由于CcVD函数与变量之间的高度复杂关系，它的精确梯度公式从未在文献中出现过。我们第一次给出了CcVD函数梯度显式计算公式，为 CcVD 的加速计算带来了突破性的进展，实验表明计算速度比原有算法加快了十倍左右。在对平面区域上CcVD的性质和快速计算方法研究成果的基础上，我们将方法推广到一般三维曲面上对CcVD的快速计算。以往关于平面上CcVD的计算方法依赖于平面区域的离散表示，比如表示为稠密的规则或者不规则点的集合，从而很难推广到曲面上。我们的方法基于空间的连续表达，推广到时曲面较为顺利。Voronoi图和Delaunay三角剖分有非常密切的关系，通过系统研究最优Delaunay剖分和重心Voronoi图的联系和区别，我们给出了快速计算最优Delaunay剖分的方法。另外，基于对最优Delaunay剖分目标函数非凸和C0连续性的观察，以往的局部优化方法一般很难得到满意的结果，因此我们提出了利用全局方法优化目标函数的想法。一般的全局优化算法时间复杂度都较高，我们利用最优Delaunay剖分目标函数的特殊性，再结合局部优化算法，给出了一个高效的全局优化算法。.在应用方面，我们将Voronoi剖分的理论应用于蓝噪声采样、网格生成、图像逼近和样条曲面的自适应节点设置等问题，取得了很好的效果。Voronoi剖分理论之所以能成功应用于这些问题，关键在于本质上它们都可以看成为是一个函数逼近问题。所以从函数逼近的角度，我们可以研究更加一般的Voronoi剖分和三角剖分的生成方法，为未来的研究打开一个全新的思路。