Uniformly sample a point per polytope

I want to uniformly sample a point within each of $10^5$ convex polytopes in each iteration of a solver.
The polytopes in one iteration are completely different from the polytopes in another iteration.
The dimension of the space is about 15.
The vertices of each polytopes are known.
I only want one point per polytope.

Hit and run sampling would take quite a lot of steps to converge to a uniform distribution.

Triangulating each polytope to simplex can work. But doing that in high dimension seems tedious (at a quick glance.)

Are there other methods to do this?

Thanks.

asked Oct 28, 2018 at 16:30

R zu

1639 bronze badges

$\begingroup$ You might find the minimal enclosing sphere (via linear programming) and then sample uniformly in the sphere until a point is inside the polytope. $\endgroup$
– Joseph O'Rourke
Commented Oct 29, 2018 at 14:05
1

$\begingroup$ Don't need linear programming to do that if I just want a rough sphere centered at average of vertices. If the polytope is thin, it will take many trials to find a point within the polytope. The situation gets worse when the dimension increases. $\endgroup$
– R zu
Commented Oct 29, 2018 at 15:20
$\begingroup$ I would think diffusion over the barycentric coordinate is faster than that if the generation of random number is the bottleneck. Maybe I can use the pdf of exponential distribution to speed up the rate of diffusion, as in sampling within a simplex:cs.stackexchange.com/questions/3227/… $\endgroup$
– R zu
Commented Oct 29, 2018 at 15:27
$\begingroup$ Yes, the enclosing sphere is only useful if your polytopes are "round." $\endgroup$
– Joseph O'Rourke
Commented Oct 29, 2018 at 15:54
$\begingroup$ See the answers to this MO question: Uniformly Sampling from Convex Polytopes. $\endgroup$
– Joseph O'Rourke
Commented Oct 29, 2018 at 15:55

| Show 1 more comment

0 Your Answer

Name

Required, but never shown

Post as a guest

Name

Required, but never shown

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.