MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)?

share|cite|improve this question
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
@alvarezpaiva, no, I haven't tried, but thanks for pointing it out. I was more thinking about triangles as the simplest examples, since in that case, there is some variety, which is not present in the case $[0,1]$. – passerby51 Nov 12 '13 at 12:16

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.