  Consider transportation of one distribution of mass onto another, chosen to
optimize the total expected cost, where cost per unit mass transported from x
to y is given by a smooth function c(x,y). If the source density f^+(x) is
bounded away from zero and infinity in an open region U' \subset R^n, and the
target density f^-(y) is bounded away from zero and infinity on its support \cl
V \subset R^n, which is strongly c-convex with respect to U', and the
transportation cost c satisfies the A3w condition of Trudinger and Wang
\cite{TrudingerWang07p}, we deduce local H\"older continuity and injectivity of
the optimal map inside U' (so that the associated potential u belongs to
C^{1,\alpha}_{loc}(\U')). Here the exponent \alpha>0 depends only on the
dimension and the bounds on the densities, but not on c. Our result provides a
crucial step in the low/interior regularity setting: in a sequel
\cite{FigalliKimMcCann09p}, we use it to establish regularity of optimal maps
with respect to the Riemannian distance squared on arbitrary products of
spheres. Three key tools are introduced in the present paper. Namely, we first
find a transformation that under A3w makes c-convex functions level-set convex
(as was also obtained independently from us by Liu \cite{Liu09}). We then
derive new Alexandrov type estimates for the level-set convex c-convex
functions, and a topological lemma showing optimal maps do not mix interior
with boundary. This topological lemma, which does not require A3w, is needed by
Figalli and Loeper \cite{FigalliLoeper08p} to conclude continuity of optimal
maps in two dimensions. In higher dimensions, if the densities f^\pm are
H\"older continuous, our result permits continuous differentiability of the map
inside U' (in fact, C^{2,\alpha}_{loc} regularity of the associated potential)
to be deduced from the work of Liu, Trudinger and Wang
\cite{LiuTrudingerWang09p}.
