MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a binary space partitioning (BSP) tree which recursively partitions a hypercube using linear hyperplanes. That is, a hyperplane splits the hybercube in half, creating two convex polytopes. Each polytope is then itself split by a hyperplane (one per polytope) and so on recursively up to some depth. This results in a partition of the hypercube into convex polytopes, where each polytope is defined by a set of linear inequalities $Ax < b$. I need to sample a certain number of points from each polytope uniformly at random. I understand there are various ways of sampling from convex polytopes (e.g. rejection sampling, MCMC), but I wonder if there is any way to exploit the structure of my problem - in particular that the polytopes form a partition - to make the sampling more efficient.

I'm considering partitions of 1,000-10,000 polytopes and sampling 100-1,000 points per polytope for dimensions up to 10-20 (i.e. in $\mathbb{R}^d$).

Edit: The ratio of the volume of the largest polytope to the volume of the smallest polytope could be as much as $2^{20}$ (possibly higher).


share|cite|improve this question
Can't you just sample points uniformly from the entire hypercube, discarding points in polytopes which already have enough points? The only reason this would be inefficient is if your polytopes have widely differing (hyper)volumes. Do they? – Keenan Pepper Sep 20 '11 at 5:12
Yes, the tree is being used to do a variable resolution discretisation of the hypercube - so "important" areas have significantly more (and hence smaller) polytopes. Off the top of my head, the maximum volume ratio between the largest and smallest polytopes could be anywhere between $2^{10}$ or $2^{20}$. What you suggest seems fairly simple to implement, so I'll give it a try and see if it works alright. Thanks! – djv Sep 20 '11 at 5:20

Your Answer


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

Browse other questions tagged or ask your own question.