Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
1  
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
3  
Have you computed the case of the segment $[0,1]$? –  alvarezpaiva Nov 12 '13 at 7:17
1  
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
show 3 more comments

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.