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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.