1
$\begingroup$
  • 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.

$\endgroup$
  • $\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 Oct 29 '18 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 Oct 29 '18 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 Oct 29 '18 at 15:27
  • $\begingroup$ Yes, the enclosing sphere is only useful if your polytopes are "round." $\endgroup$ – Joseph O'Rourke Oct 29 '18 at 15:54
  • $\begingroup$ See the answers to this MO question: Uniformly Sampling from Convex Polytopes. $\endgroup$ – Joseph O'Rourke Oct 29 '18 at 15:55

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.