Newton-Okounkov bodies of exceptional curve valuations

We prove that the Newton-Okounkov body of the flag $E_{\bullet}:= \left\{ X=X_r \supset E_r \supset \{q\} \right\}$, defined by the surface $X$ and the exceptional divisor $E_r$ given by any divisorial valuation of the complex projective plane $\mathbb{P}^2$, with respect to the pull-back of the line-bundle $\mathcal{O}_{\mathbb{P}^2} (1)$ is either a triangle or a quadrilateral, characterizing when it is a triangle or a quadrilateral. We also describe the vertices of that figure. Finally, we introduce a large family of flags for which we determine explicitly their Newton-Okounkov bodies which turn out to be triangular.