Coarse-to-Fine: Hierarchical Incremental Acceleration for Solving Exact Semi-Discrete Optimal Transport

Monte Carlo (MC)-based geometric variational methods address the intractability of analytical Power-Voronoi cell volume computation for semi-discrete optimal transport. However, their global cold-start synchronous iteration incurs drastically rising partitioning cost as target points scale up, severely slowing total solving efficiency. To mitigate this limitation, this paper proposes a hierarchical fast solving framework. First, we preprocess target points and partition them layer by layer in a nearest-to-farthest order. Second, we combine the head and tail layers to build global skeleton that locks the overall Power diagram topology in advance. In incremental updates, each point in every newly added layer is initialized with the Brenier height of its nearest solved neighbor. Using converged layer outputs for warm-start refinement, we sequentially solve optimal Brenier heights for all targets layer by layer. Experiments on standard and complex real-world distributions show that our approach achieves an average 53.88% acceleration versus the original MC solver, with stable permille-scale error between solved Brenier heights and ground truth. Supplementary tests on generative modeling, adversarial attacks and out-of-distribution overconfidence further confirm that our method causes only negligible percentage-to-permille scale performance deviations in downstream tasks.