Centroidal Power Diagrams with Capacity Constraints: Computation, Applications, and Extension
Centroidal Power Diagrams with Capacity Constraints: Computation, Applications, and Extension
复制标题
具有容量约束的质心功率图：计算、应用和扩展
DOI：
10.1145/2980179.2982428
复制
发表时间：
2016
影响因子：
6.2
通讯作者：
Wang Wenping
中科院分区：
文献类型：
--
作者：
Xin Shi-Qing;Levy Bruno;Chen Zhonggui;Chu Lei;Yu Yaohui;Tu Changhe;Wang Wenping
本文提出了一种新的方法来最优地划分一个几何区域的容量限制的划分区域。它是从工程到经济的许多领域中的一个重要问题。众所周知，容量受限的划分可以作为具有平方L2度量的幂函数来获得。我们提出了一种超线性收敛的方法来计算最优分割的容量限制，优于国家的最先进的一个数量级。我们在计算机图形和几何处理中的三种不同应用中证明了我们方法的效率：函数分布的位移插值、蓝噪声点采样和2D域的最佳凸分解。此外，所提出的方法被扩展到容量约束的最优划分的一般成本函数超过平方欧几里德距离。
This article presents a new method to optimally partition a geometric domain with capacity constraints on the partitioned regions. It is an important problem in many fields, ranging from engineering to economics. It is known that a capacity-constrained partition can be obtained as apower diagramwith the squared L2 metric. We present a method with super-linear convergence for computing optimal partition with capacity constraints that outperforms the state-of-the-art in an order of magnitude. We demonstrate the efficiency of our method in the context of three different applications in computer graphics and geometric processing: displacement interpolation of function distribution, blue-noise point sampling, and optimal convex decomposition of 2D domains. Furthermore, the proposed method is extended to capacity-constrained optimal partition with respect to general cost functions beyond the squared Euclidean distance.