Centroidal power diagrams with capacity constraints

Shi-Qing Xin (1) , Bruno Lévy (2) , Zhonggui Chen (3) , Lei Chu (4) , Yaohui Yu (4) , Changhe Tu (5)

1 University of Nottingham Ningbo [China]
2 ALICE - Geometry and Lighting
3 Xiamen University
4 HKU - The University of Hong Kong
5 Shandong University

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 a power diagram with 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 Eu-clidean distance.

Mots clés: centroidal power diagram; displacement interpolation; convex decomposition; blue noise; Concepts: •Computing methodologies → Computer graphics

Domaines: Synthèse d'image et réalité virtuelle [cs.GR]

Shi-Qing Xin, Bruno Lévy, Zhonggui Chen, Lei Chu, Yaohui Yu, et al.. Centroidal power diagrams with capacity constraints. Siggraph asia 2016, Dec 2016, macao, Macau SAR China. pp.1 - 12, ⟨10.1145/2980179.2982428⟩. ⟨hal-01401949⟩