Fast and Accurate Cost-Scaling Algorithm for the Semi-Discrete Optimal Transport

Given a continuous probability distribution $\mu$ and a discrete distribution $\nu$ in the $d$-dimensional space, the semi-discrete Optimal Transport (OT) problem asks for computing a minimum-cost plan to transport mass from $\mu$ to $\nu$. In this paper, given a parameter $\varepsilon >0$, we present an approximation algorithm that computes a semi-discrete transport plan $\tau$ with cost $\textcent(\tau) \le \textcent(\tau^*)+\varepsilon$ in $n^{O(d)}\log\frac{C_{\max}}{\varepsilon}$ time; here, $\tau^*$ is the optimal transport plan, $C_{\max}$ is the diameter of the supports of $\mu$ and $\nu$, $n$ is the number of points in the support of the discrete distribution, and we assume we have access to an oracle that outputs the mass of $\mu$ inside a constant-complexity region in $O(1)$ time. Our algorithm works for several ground distances including the $L_p$-norm and the squared-Euclidean distance.