Convex bodies appearing as Okounkov bodies of divisors

Based on the work of Okounkov (\cite{Ok96}, \cite{Ok03}), Lazarsfeld and Musta\c t\u a (\cite{LM08}) and Kaveh and Khovanskii (\cite{KK08}) have independently associated a convex body, called the Okounkov body, to a big divisor on a smooth projective variety with respect to a complete flag. In this paper we consider the following question: what can be said about the set of convex bodies that appear as Okounkov bodies? We show first that the set of convex bodies appearing as Okounkov bodies of big line bundles on smooth projective varieties with respect to admissible flags is countable. We then give a complete characterisation of the set of convex bodies that arise as Okounkov bodies of $\R$-divisors on smooth projective surfaces. Such Okounkov bodies are always polygons, satisfying certain combinatorial criteria. Finally, we construct two examples of non-polyhedral Okounkov bodies. In the first one, the variety we deal with is Fano and the line bundle is ample. In the second one, we find a Mori dream space variety such that under small perturbations of the flag the Okounkov body remains non-polyhedral.