Scalable Capacity‐Constrained Power Diagrams via Compressed Optimal Assignment

Abstract 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 .

Authors

Institutions

Publication Details

Journal
Computer Graphics Forum
Published
2026-11-14
DOI
https://doi.org/10.1111/cgf.70609
Primary Topic
Computational Geometry and Mesh Generation
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

Scalable Capacity‐Constrained Power Diagrams via Compressed Optimal Assignment

Jiantao Song, Shuangmin Chen, Yunqi Yang, Shiqing Xin et al.
Computer Graphics Forum
Computational Geometry and Mesh Generation
article

Scalable Capacity‐Constrained Power Diagrams via Compressed Optimal Assignment

Jiantao Song, Shuangmin Chen, Yunqi Yang, Shiqing Xin, Changhe Tu
article en

Abstract

Abstract 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 .

Computer Graphics Forum
Qingdao University of Science and Technology (CN), Shandong University (CN)
Computational Geometry and Mesh Generation
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon