ABSTRACT

First, we review the semi-discrete optimal transport problem and its relation to a Laguerre tessellation.  Then, we propose a new method for solving the semi-discrete optimal transport problem for cost functions that are a positive combination of $p$-norms, $1<p<\infty$.

By exploiting the geometry of the Laguerre cells, we obtain an efficient and reliable implementation of Newton's method to find the sought subdivision.  We give implementation details and some numerical results.