I need to deal with the following. Let $[B]$ denote the set of integers $\{0,1,\ldots,B\}$.

Consider an integer $n \geq 3$ and a grid $[B]\times [B]$, and let $P_{n,B}$ denote the set of convex polytopes in $[B]\times [B]$ of $n$ vertices. How do we sample a uniform element in $P_{n,B}$?

In other words, I need an algorithmic to uniquely generate all the convex polytopes of a given number of vertices.

For instance, if $n=3$, then we can simply sample any three different points in $[B]\times[B]$, since they automatically define a convex polytope of three vertices. However, for $n>3$ this does not work since $n$ points may not define a convex polytope.

I assumed this problem has been studied before. Anyone has some insights?


  • $\begingroup$ I assume you've considered rejection sampling? Pick any $n$ distinct points, take their convex hull, accept it if it has $n$ vertices, otherwise try again. Note that you'll have to do this even when $n=3$, since the points may be collinear. $\endgroup$ – Rahul Oct 11 '18 at 12:11
  • $\begingroup$ @Rahul Thanks Rahul. Definitely, that's our standard approach, but it scales very badly since, when you increase $n$, the probability of getting a convex hull with a large number of nodes (relatively close to $n$) goes down rather quickly. (Thanks for pointing out the issue with $n=3$ :-) ) $\endgroup$ – Daniel Oct 11 '18 at 12:12
  • $\begingroup$ Have you searched some of these links? google.com/… ? The requirement for grid points might be the stumbling block. $\endgroup$ – Ethan Bolker Oct 11 '18 at 14:23

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.