Answers are grounded in this paper and cite their sources.
Power diagrams with prescribed capacities are widely used in geometry processing, including blue‐noise sampling, remeshing, and constrained clustering. The problem can be viewed as a semi‐discrete optimal transport problem and is commonly discretized by dense sampling into a capacity‐constrained assignment between n samples and m sites. Since this assignment is repeatedly solved in Lloyd‐type optimization, its efficiency is crucial to scalability. We propose an exact algorithm for the resulting discrete capacity‐constrained assignment problem. Unlike general‐purpose minimum‐cost flow solvers, which treat the input as an abstract graph, and entropic‐regularized approximations, which sacrifice exactness, our method exploits the asymmetry m ≪ n between sites and samples, performing augmentations on a compressed auxiliary graph with only m + 2 nodes while maintaining point‐level transfer costs using priority queues. We prove that augmenting paths in the full residual network can be projected to bounded‐length walks on the auxiliary graph, yielding an O(nm 2 log n) running time and near‐linear scaling in the number of samples for fixed m. Experiments on synthetic data and geometry‐processing tasks show that our method achieves one or two orders of magnitude speedup over classical algorithms while preserving exact optimality for the discrete transport problem, enabling efficient computation of capacity‐constrained power diagrams in large‐scale sampled settings .
No takes yet. Share an insight, caveat, or question.
Song et al. (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: