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

Abstract

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 any parameter $\varepsilon>0$, we present an algorithm that computes a semi-discrete transport plan $\tilde\tau$ with cost $\textcent(\tilde\tau) \le \textcent(\tau^*)+\varepsilon$ in $n^{O(d)}\log\frac{\mathrm{D}}{\varepsilon}$ time; here, $\tau^*$ is the optimal transport plan, $\mathrm{D}$ is the diameter of the supports of $\mu$ and $\nu$, 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.