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 a parameter $\epsilon >0$, we present an approximation algorithm that computes a semi-discrete transport plan $\tau$ with cost $\text{textcent}(\tau )\le \text{textcent}({\tau }^{\ast })+\epsilon$ in $n^{O(d)}\log \frac{C_{max}}{\epsilon }$ time; here, ${\tau }^{\ast }$ 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.