Large-scale semi-discrete optimal transport with distributed Voronoi diagrams (www.sciencedirect.com)

Researchers introduced a scalable method for solving semi-discrete optimal transport (OT) problems by building distributed Voronoi (power/Laguerre) diagram infrastructure that lets the OT dual be optimized across many machines. Semi-discrete OT — mapping a continuous density to a discrete set of target masses — reduces to finding weights that define weighted Voronoi cells whose volumes match target masses. The paper shows how to distribute the heavy work of computing and updating these cells (cell geometry, integrals of the source density, and weight updates) across processors with spatial partitioning, local communication, and efficient geometric kernels, enabling practical solution of much larger problems than single-node implementations allow. This is significant for ML and computational geometry because semi-discrete OT underpins barycenters, continuous-to-discrete map construction, and OT-based losses in large models, but was previously limited by CPU/GPU and memory bottlenecks. By combining distributed power-diagram construction, communication-aware synchronization of dual variables, and scalable numerical solvers for the concave dual (gradient/Newton-style updates), the approach delivers robust convergence and far better throughput for high-resolution densities and large target point sets. The result opens up OT applications at scales needed for city-scale resource allocation, high-resolution generative modeling and graphics, and large-batch OT training workflows.