Return to Question

added 148 characters in body

Source Link

edited Sep 20, 2011 at 5:21

31
2

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!

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

Thanks!

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!

Source Link

asked Sep 20, 2011 at 4:35

31
2

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

Thanks!

sampling convex-polytopes polytopes partitions