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

0

Your Answer

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

Browse other questions tagged or ask your own question.