Procedure to generate 2-dimensional convex polytopes with a given number of vertices

31 Views Asked by At

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?

Thanks!