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

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!

• 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. – Rahul Oct 11 at 12:11
• @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$ :-) ) – Daniel Oct 11 at 12:12
• Have you searched some of these links? google.com/… ? The requirement for grid points might be the stumbling block. – Ethan Bolker Oct 11 at 14:23