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

• You might find the minimal enclosing sphere (via linear programming) and then sample uniformly in the sphere until a point is inside the polytope. – Joseph O'Rourke Oct 29 '18 at 14:05
• 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. – R zu Oct 29 '18 at 15:20
• 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/… – R zu Oct 29 '18 at 15:27
• Yes, the enclosing sphere is only useful if your polytopes are "round." – Joseph O'Rourke Oct 29 '18 at 15:54
• See the answers to this MO question: Uniformly Sampling from Convex Polytopes. – Joseph O'Rourke Oct 29 '18 at 15:55