In the eighteenth century Gaspard Monge considered the problem of finding the best way of moving a pile of material from one site to another. This optimal transport problem has many applications such as mesh generation, moving mesh methods, image registration, image morphing, optical design, cartograms, probability theory, etc. The solution to an optimal transport problem can be found by solving the Monge-Amp\`{e}re equation, a highly nonlinear second order elliptic partial differential equation. Leonid Kantorovich, however, showed that it is possible to analyse optimal transport problems in a framework that naturally leads to a linear programming formulation. In recent years several efficient methods have been proposed for solving the Monge-Amp\`{e}re equation. For the linear programming problem, standard methods do not exploit the special properties of the solution and require a number of operations that is quadratic or even cubic in the number of points in the discretisation. In this talk I will discuss techniques that can be used to obtain more efficient methods.
Joint work with Chris Budd (University of Bath).