Centroidal Power Diagrams with Capacity Constraints: Computation, Applications, and Extension

摘要

This article presents a new method to optimally partition a geometricrndomain with capacity constraints on the partitioned regions.rnIt is an important problem in many fields, ranging from engineeringrnto economics. It is known that a capacity-constrained partitionrncan be obtained as a power diagram with the squared L2 metric.rnWe present a method with super-linear convergence for computingrnoptimal partition with capacity constraints that outperforms thernstate-of-the-art in an order of magnitude. We demonstrate the efficiencyrnof our method in the context of three different applicationsrnin computer graphics and geometric processing: displacement interpolationrnof function distribution, blue-noise point sampling, andrnoptimal convex decomposition of 2D domains. Furthermore, thernproposed method is extended to capacity-constrained optimal partitionrnwith respect to general cost functions beyond the squared Euclideanrndistance.