# How to sample from a convex hull?

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.

• 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. – joriki Jul 17 '15 at 14:41