  Let M and \bar M be n-dimensional manifolds equipped with suitable Borel
probability measures \rho and \bar\rho. Ma, Trudinger & Wang gave sufficient
conditions on a transportation cost c \in C^4(M \times \bar M) to guarantee
smoothness of the optimal map pushing \rho forward to \bar\rho; the necessity
of these conditions was deduced by Loeper. The present manuscript shows the
form of these conditions to be largely dictated by the covariance of the
question; it expresses them via non-negativity of the sectional curvature of
certain null-planes in a novel but natural pseudo-Riemannian geometry which the
cost c induces on the product space M \times \bar M.
  H\"older continuity of optimal maps was established for rougher mass
distributions by Loeper, still relying on a key result of Trudinger & Wang
which required certain structure on the domains and the cost. We go on to
develop this theory for mass distributions on differentiable manifolds --
recovering Loeper's Riemannian examples such as the round sphere as particular
cases -- give a direct proof of the key result mentioned above, and revise
Loeper's H\"older continuity argument to make it logically independent of all
earlier works, while extending it to less restricted geometries and cost
functions even for subdomains M and \bar M of R^n. We also give new examples of
geometries satisfying the hypotheses -- obtained using submersions and tensor
products -- and some connections to spacelike Lagrangian submanifolds in
symplectic geometry.
