The distribution of barycentric coordinates

Solution 1:

I can propose the next algorithm for picking the point from the polytope:

1. Firstly, triangulate your polytope (it is simple for convex ones).

2. Calculate an absolute values of hypervolumes of simplexes from 1. (hypervolume is just a determinant of $d \times d$-matrix of rows as vectors from last vertex to each of first $d$ vertices divided by $d!$). Then transform above set to partial sums set. Generate uniformly distributed value from zero to sum of hypervolumes. By means of binary search in above set you can choose the simplex $P = \{\mathbf{p}_i\}_{i = 0}^d$.

3. For this simplex do:

   1. Step $0$: $\mathbf{p} \leftarrow \mathbf{p}_0$
   2. Step $i$: $w_i = (U[0;1])^\frac{1}{i},\; \mathbf{p} \leftarrow \mathbf{p} * w_i + \mathbf{p}_i \cdot (1 - w_i)$

   On the $d$-th step ($d + 1$ totally, due to $i$ is zero-based index) you will peak the desired uniformly distributed point $\mathbf{p}$ inside the simplex $P$.

I don't know how calls the resulted distributions of baricentric coordinates, but geometrical interpretation of the algorithm is evident: on $i$-th step consequentely we add barycentric dimension from next in turn vertex relative to its opposite $i - 1$-dimensional simplex $S_{i - 1}$ (which is defined by set of vertices$\stackrel{def}{=} \{\mathbf{p}_j\}_{j = 0}^{i - 1}$), formed by all previously involved vertices. $i$-hypervolume of pyramid formed by $S_{i - 1}$ and secant (also $i - 1$-simplex) of simplex $S_i$, which is parallel to the $S_{i - 1}$ simplex, distributed as $\frac{1}{i} \cdot V_{i - 1} \cdot \displaystyle\sqrt[\displaystyle i]{h_i}$, where $V_{i - 1}$ is $i - 1$-hypervolume of $S_{i - 1}$ and $h_i \in [0;h_{0i}]$ is distance from the secant of $S_i$ to $S_{i - 1}$ and $h_{0i}$ is distance from $\mathbf{p}_i$ vertex to $S_{i - 1}$; $h_i$ distributed uniformly as stated in statement.

If the number of resulted points is known at the start, then we can reduce the step 2.: generate respective part of whole amount of resulted points for each $d$-simplex.

Also, I suspect, that numerical stability is very-very bad for higher dimensions, due to recurrent nature of step 3. and high degrees of roots.

There is alternative approach using standard unit $d - 1$-simplex mentioned here. As mentioned above, affine transformations does not affect on barycentric coordinates, and, as I know, on uniformity of the distribution. So, the answer on the question is: the distribution of the coordinates is Dirichlet distribution. It looks quite "symmetrical" and, on my mind, numerical stable, but requires one more uniformly distributed value.

$Y_i \sim \operatorname{Gamma}(1,1) = \operatorname{Exp}(1), i \in \{1, 2, \dots, dim\} \\ V = \sum \limits_{i = 1}^{dim}Y_i \sim \operatorname{Gamma}(\underbrace{\sum \limits_{i = 1}^{dim}1}_\text{= dim}, 1) \\ X = (X_1, X_2, \dots, X_{dim}) = (\frac{Y_1}{V}, \frac{Y_2}{V}, \dots, \frac{Y_{dim}}{V}) \sim \operatorname{Dir}(\underbrace{1, 1, \dots, 1}_\text{dim times})$

Solution 2:

It seems the following.

We have no unique choice of $\alpha$. For instance, let $d=2$ and $\mathcal{X}$ be a set of vertices of a regular hexagon $H.$ Let $\mathcal{X_1}$ be a set of odd vertices of $H$ and $\mathcal{X_2}$ be a set of even vertices of $H$. Then each point $z$ from the intersetion of triangles $\text{conv}(\mathcal{X}_1)$ and $\text{conv}(\mathcal{X}_2)$ has two natural choices of its $\alpha$. Moreover, it seems that we have a unique choice of $\alpha=\alpha(z)$ for each point $z\in \text{conv}(\mathcal{X})$ iff $\mathcal{X}$ is a set of vertices of a simplex.