# Sampling from a partition of a hypercube by convex polytopes.

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).

Thanks!

-
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