Let us consider a couple of points $x^{(i)}\in \mathbb{R}^m$ where $i=1,\dots,n$. Convex hull is defined as $$ C = \left\{\sum_{i=1}^{m} \alpha_i x^{(i)} \mathrel{\Bigg|} (\forall i: \alpha_i\ge 0)\wedge \sum_{i=1}^{m} \alpha_i=1 \right\} $$ My question is: how to sample uniformly from $C$?

My attempt: to construct a hyper-box covering $C$ and sample new and new points from the hull until $C$ is reached. If $C$ is no-zero measure, than this is just question of time.

I wonder if you know something smarter.

  • 1
    $\begingroup$ Here's a rather impractical method: Sample uniformly from $(\alpha_1,\ldots,\alpha_m)\in[0,1]^m$, then calculate the volume of $[0,1]^m$ that would have yielded the same convex combination and inversely weight the sample with that volume. $\endgroup$ – joriki Jul 17 '15 at 14:41

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.