2
$\begingroup$

I would like to generate points that are uniformly distributed over the SURFACE of a standard $k$-simplex ($k$ dimensions, $k+1$ vertices).

One way to efficiently generate points that are uniformly distributed over the ENTIRETY of the $k$-simplex is to generate samples of $k$ iid exponential random variables, $E_i$, $i\in \left[1,k\right]$, then normalize, and $\vec{X}=\frac{\left\langle E_1,E_2,\dots,E_k\right\rangle}{\sum_{i=1}^k E_i}$, will be uniformly distributed over the entire $k$-simplex.

My problem is that the probability that one of these points lands on the surface (i.e. at a vertex, or along a hyper-edge, or on hyper-face, etc.) is nearly $0$, so that in practice all of the points end up being in the INTERIOR of the $k$-simplex.

In an attempt to sample the SURFACE of the $k$-simplex I have considered each hyper-edge, hyper-face, etc. separately and generated uniformly distributed samples on each (since they are themselves lower dimensional simplices). However, the problem becomes computationally unfeasible as $k$ increases because the number of hyper-edges, hyper-faces, etc. blows up.

Does anyone know of a method to explicitly generate samples that are uniformly distributed over the SURFACE (or BOUNDARY) of a standard $k$-simplex?

$\endgroup$
2
$\begingroup$

Notice that faces of higher codimension than $1$ are negligible (they have measure zero), so to generate your random point you just need to:

  1. Pick a random integer from $0$ to $k.$ That will tell you which (top dimensional) face of the surface of the simplex you are working with.

The top dimensional faces are themselves simplices, so

  1. Use the algorithm you describe to generate a random point on the face you chose.

EDIT For the OP's nonuniform question, the simplest solution is to do what I said before, but if the point is too close to the boundary of the face (so, in three dimensions, you are picking a point from a triangular face, and seeing if it is too close to the edge), go to the closest point of that boundary, and then iterate the process.

$\endgroup$
  • $\begingroup$ That is a great insight. However, in spite of the fact that faces of higher codimension that 1 have measure zero, points on such faces are often more important for my application. In fact, my interest in a given face decreases slightly with decreasing codimension :), so I somehow need to uniformly sample all faces regardless of co-dimension, without explicitly considering each face, since the number of faces blows up. $\endgroup$ – okj Dec 18 '13 at 15:57
  • $\begingroup$ @okj in that case, I am not sure what you are looking for, because any uniform sampling method will get you $0$ points on higher codimension faces on average. $\endgroup$ – Igor Rivin Dec 18 '13 at 16:04
  • $\begingroup$ @okj so you are looking for something non-uniform, in which case you need to be precise about what it is... $\endgroup$ – Igor Rivin Dec 18 '13 at 16:05
  • $\begingroup$ A geometrical example might help. Consider a 3-simplex (a tetrahedron), the final sample set should consist of points on edges, and faces (if it doesn't get the vertices that's ok, they are easy to add), and the number of points from each edge (or face) should be roughly equal. The average number of points on an edge should be less that the average number of points on a face, for example, if, on average, there are $10^1$ points on an edge, then, on average, there should be maybe $10^2$ points on a face. $\endgroup$ – okj Dec 18 '13 at 16:53
  • $\begingroup$ @okj see the edit... $\endgroup$ – Igor Rivin Dec 18 '13 at 19:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.