  Given two probability measures $\mu$ and $\nu$ in "convex order" on $\R^d$,
we study the profile of one-step martingale plans $\pi$ on $\R^d\times \R^d$
that optimize the expected value of the modulus of their increment among all
martingales having $\mu$ and $\nu$ as marginals. While there is a great deal of
results for the real line (i.e., when $d=1$), much less is known in the richer
and more delicate higher dimensional case that we tackle in this paper. We show
that many structural results can be obtained whenever a natural dual
optimization problem is attained, provided the initial measure $\mu$ is
absolutely continuous with respect to the Lebesgue measure. One such a property
is that $\mu$-almost every $x$ in $\R^d$ is transported by the optimal
martingale plan into a probability measure $\pi_x$ concentrated on the extreme
points of the closed convex hull of its support. This will be established in
full generality in the 2-dimensional case, and also for any $d\geq 3$ as long
as the marginals are in "subharmonic order". In some cases, $\pi_x$ is
supported on the vertices of a $k(x)$-dimensional polytope, such as when the
target measure is discrete. Many of the proofs rely on a remarkable
decomposition of "martingale supporting" Borel subsets of $\R^d\times \R^d$
into a collection of mutually disjoint components by means of a "convex paving"
of the source space. If the martingale is optimal, then each of the components
in the decomposition supports a restricted optimal martingale transport for
which the dual problem is attained. These decompositions are used to obtain
structural results in cases where duality is not attained. On the other hand,
they can also be related to higher dimensional Nikodym sets. %On the other
hand, they can also lead to natural and intriguing constructions of higher
dimensional Nikodym sets.
