EUVIMEDEUVIMED entdecken
Crossref

Scalable Capacity‐Constrained Power Diagrams via Compressed Optimal Assignment

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

Computer Graphics Forum · 14.11.2026

DOI: 10.1111/cgf.70609 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Computer Graphics Forum, online erschienen am 14.11.2026. Verfasst von Jiantao Song und 4 weiteren Autor:innen. Die Arbeit nennt 28 Literaturangaben. Gefördert von: National Natural Science Foundation of China.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 .

Förderung

  • National Natural Science Foundation of China

Zitieren

APA

Song, J., Yang, Y., Chen, S., Tu, C., & Xin, S. (2026). Scalable Capacity‐Constrained Power Diagrams via Compressed Optimal Assignment. Computer Graphics Forum. https://doi.org/10.1111/cgf.70609

Vancouver

Song J, Yang Y, Chen S, Tu C, Xin S. Scalable Capacity‐Constrained Power Diagrams via Compressed Optimal Assignment. Computer Graphics Forum. 2026. doi:10.1111/cgf.70609

BibTeX
@article{Song2026,
  author = {Song, Jiantao and Yang, Yunqi and Chen, Shuangmin and Tu, Changhe and Xin, Shiqing},
  title = {Scalable Capacity‐Constrained Power Diagrams via Compressed Optimal Assignment},
  journal = {Computer Graphics Forum},
  year = {2026},
  doi = {10.1111/cgf.70609}
}
Kostenlos starten →