The boundary method for semi-discrete optimal transport partitions and Wasserstein distance computation
arXiv:1702.03517 · doi:10.1016/j.cam.2018.12.034
Abstract
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.
37 pages, 24 figures (including subfigures), 10 tables (including subtables)