Let $T$ be the triangle whose vertices are three given points $\mathbf{x}, \mathbf{y}, \mathbf{z}\in\mathbb{R}^d$.




---


**Question**: What ***computationally efficient*** strategy can we use to sample a point $\mathbf{p}$ from $T$ with probability linearly proportional to $\|\mathbf{p}\|\_2$?



Geometric sampling problem in the Euclidean space in high dimensions
It doesn't make any difference that $d\gg 1$. If $0<a<b<1$, $Q(a,b)=\|a\mathbf x+(b-a)\mathbf y+(1-b)\mathbf z\|\_2^2=a^2\|\mathbf x\|^2+(b-a)^2\|\mathbb y\|^2+(1-b)^2\|\mathbf z\|^2+2a(b-a)\langle\mathbf x,\mathbf y\rangle+2(b-a)(1-b)\langle\mathbf x,\mathbf z\rangle$. That is, you should pick the point in the 2d simplex $\{(a,b)\colon 0<a<b<1\}$ with probability proportional to $\sqrt {Q(a,b)}$. This is then mapped to the point in your original triangle by $(a,b)\mapsto a\mathbf x+(b-a)\mathbf y+(1-b)\mathbf z$ (this mapping is linear, and so a proportion $t$ of the simplex maps to a proportion $t$ of the triangle).


