ACombinatorialAlgorithmfortheSemi-Discrete OptimalTransportProblem

In the semi-discrete2-Wasserstein problem, we wish to compute the cheapest way to transport all the mass from a continuous distribution µ to a discrete distributionν in Rd for d 1, where the cost of transporting unitmassbetween pointsaandbisd(a,b)= a b 2. When both distributions are discrete, a simple combinatorial framework has been used to find the exact solution (see e.g.