# Wasserstein distance, convex polytopes and extreme points

Let us consider convex polytopes with $K$ extreme points in $\mathbb{R}^d$. Let $\mathbf{P}$ be such polytope, and let $\text{ext}(\mathbf{P})$ denote its set of extreme points, so that $\mathbf{P} = \text{conv}(\text{ext}(\mathbf{P}))$ and $|\text{ext}(\mathbf{P})| =K$.

Let $\mathcal{L}|_{\mathbf{P}}$ be the uniform distribution on $\mathbf{P}$, or in other words, the restriction of $d$-dimensional Lebesgue measure to $\mathbf{P}$. Also, let $$\mathbb{P}_{\mathbf{P}} := \frac{1}{K} \sum_{x \in \text{ext}(\mathbf{P})} \delta_x$$ be the empirical measure on the extreme points of $\mathbf{P}$, that is the discrete uniform distribution on $\text{ext}(\mathbf{P})$.

Consider Wasserstein-$p$ distance between probability measures, for $p=1$ or $2$. We are interested in $$W_p(\mathbb{P}_{\mathbf{P}},\mathcal{L}|_{\mathbf{P}}).$$ Is there a way to characterize it? For what polytopes $\mathbf{P}$, this distance is the smallest (largest)?

• Do you consider the polytope $P$ to be the set of points on or inside the hull, or is $P$ the boundary of the hull? Presumably you mean the former. – Joseph O'Rourke Nov 12 '13 at 1:58
• Yes, the I mean the former. – passerby51 Nov 12 '13 at 4:59
• Have you computed the case of the segment $[0,1]$? – alvarezpaiva Nov 12 '13 at 7:17
• You should also state the metric on $\mathbb{R}^d$ you use (presumably the euclidean metric). – Dirk Nov 12 '13 at 7:39
• And incidentally, the distance can be made arbitrarily large or small unless you impose some other constraint (fixed volume, perhaps?). – Mark Meckes Nov 13 '13 at 11:46