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

  • 1
    $\begingroup$ 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. $\endgroup$ – Joseph O'Rourke Nov 12 '13 at 1:58
  • $\begingroup$ Yes, the I mean the former. $\endgroup$ – passerby51 Nov 12 '13 at 4:59
  • 3
    $\begingroup$ Have you computed the case of the segment $[0,1]$? $\endgroup$ – alvarezpaiva Nov 12 '13 at 7:17
  • 1
    $\begingroup$ You should also state the metric on $\mathbb{R}^d$ you use (presumably the euclidean metric). $\endgroup$ – Dirk Nov 12 '13 at 7:39
  • 1
    $\begingroup$ And incidentally, the distance can be made arbitrarily large or small unless you impose some other constraint (fixed volume, perhaps?). $\endgroup$ – Mark Meckes Nov 13 '13 at 11:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.