||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 x 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, 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 for the distance cost c(x, y) = vertical bar x - y vertical bar in the two-dimensional case, and also for any d >= 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. Duality plays a crucial role in our approach, even though, in contrast to standard optimal transports, the dual extremal problem may not be attained in general. We show however that "martingale supporting" Borel subsets of R-d x R-d can be decomposed into a collection of mutually disjoint components by means of a "convex paving" of the source space, in such a way that when the martingale is optimal for a general cost function, each of the components then supports a restricted optimal martingale transport whose dual problem is attained. This decomposition is used to obtain structural results in cases where global duality is not attained. On the other hand, it shows that certain "optimal martingale supporting" Borel sets can be viewed as higher-dimensional versions of Nikodym-type sets. The paper focuses on the distance cost, but much of the results hold for general Lipschitz cost functions.