J. D. Walsh

Luca Dieci, J. D. Walsh

We introduce a new technique, which we call the boundary method, for solving semi-discrete optimal transport problems with a wide range of cost functions. The boundary method reduces the effective dimension of the problem, thus improving complexity. For cost functions equal to a p-norm with p in (1,infinity), we provide mathematical justification, convergence analysis, and algorithmic development. Our testing supports the boundary method with these p-norms, as well as other, more general cost functions.

J. D. Walsh

Semi-discrete transport can be characterized in terms of real-valued shifts. Often, but not always, the solution to the shift-characterized problem partitions the continuous region. This paper gives examples of when partitioning fails, and offers a large class of semi-discrete transport problems where the shift-characterized solution is always a partition.