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!
