Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

There are some pretty simple methods to do uniform sampling on the surface of high-dimensional spheres or cubes. Are there any methods that sample uniformly on the surface of a high-dimensional polytope?

Given a high-dimensional polytope like this:

$\| A \mathbf{x} \|_{\infty} = 1$

where $A$ is a given $m \times n$ matrix and $\mathbf{x}$ is a $n \times 1$ vector.

We want to sample a set of $\{ s_1, s_2, \dots, s_n \}$ that lie uniformly on the surface of this polytope.

I'm looking at some advanced Monte Carlo Methods, but it's not that easy.

To make the problem simpler, can we find some methods that can do infinite (non-uniform) sampling on the surface of the polytope?

share|improve this question

1 Answer 1

up vote 3 down vote accepted

Your question is ambiguous: from the title, it seems that you want to sample uniformly from the interior of the convex polytope. This is a heavily studied area, see for example this question or this paper by Diaconis, Lebeau, Michel (which came a couple of years later than the question). Sampling from the surface of a polytope has been studied much less, and I assume that it is even harder (the obvious way is to generate a list of faces, and apply the volume sampling algorithms to those; if your polytope is given as an intersection of of halfgpaces, this is roughly as hard, but if it is given as a convex hull, the number of faces could be exponential in the size of the input).

share|improve this answer
Sorry for the ambiguity and thank you very much for the response. I have fixed my title. –  Mark May 26 '12 at 15:23

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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