Random points inside a convex polytope

929 Views Asked by At

Given a convex polytope, defined by set of vertices $P = \{\mathbf{x}^{(i)}\}_{i = 1}^n, x^{(i)} = (x^{(i)}_1, x^{(i)}_2, \dots, x^{(i)}_d): \operatorname{conv}(P) = P$.

How to generate uniformely distributed points inside a convex polytope without rejection operation (i.e. "inline")?

I know only the solution of simpliest connected problem in $d$-dimensional space: sampling uniformly at random from a $d - 1$-dimensional unit simplex. To perform such sampling inline, there need only the $d$ uniformely distributed random values for each d-dimensional point of $d - 1$-simplex. So, there is some kind of projection (transformation) of ${(\operatorname{uniform}[0;1])}^d$ (hypercube, consist of $d$ uniformely distributed values) onto $\sum\limits_{j = 1}^dx_j=1$ plane.

Internals of a convex polytope can be expressed as $V = \{\mathbf{x}^{(0)} \;|\; x_j^{(0)} = \sum\limits_{i = 1}^n c_j^{(i)} \cdot x_j^{(i)}, c_j^{(i)} \in [0;1], \sum\limits_{i = 1}^n c_j^{(i)} = 1\}$, but how to infer the form of distribution of random numbers $c_j^{(i)}$ is the issue. I suspect, that the form is (maybe some generalization) of Gamma distribution, but how to infer the parametres -- I don't know.

EDIT:

This question is duplicate. I answered a similar question.

1

There are 1 best solutions below

1
On

If you can afford prior decomposition of the polytope into symplexes then choose a random symplex with probability distribution corresponding to symplexes' (hyper)volumes, then choose a point randomly within a symplex. Will work also for concave and not connected polytopes (sets of polytopes).