  We design an efficient and constructive algorithm to decompose any
generalized quantum measurement into a convex combination of extremal
measurements. We show that if one allows for a classical post-processing step
only extremal rank-1 POVMs are needed. For a measurement with $N$ elements on a
$d$-dimensional space, our algorithm will decompose it into at most $(N-1)d+1$
extremals, whereas the best previously known upper bound scaled as $d^2$. Since
the decomposition is not unique, we show how to tailor our algorithm to provide
particular types of decompositions that exhibit some desired property.
