# A question about simple closed plane polygons

For any positive integer $n$ greater than $3$, let $P(1),P(2),...,P(n)$ be a set of $n$ pairwise distinct points in the Euclidean plane, no three of which are collinear. Let $H(P(1),P(2),...,P(n))$ be the set of simple closed (not necessarily convex) polygons whose set of vertices is exactly the set $P(1),P(2),...,P(n)$. Partition $H(P(1),P(2),...,P(n))$ into equivalence classes, with two polygons in the same class just in case they are congruent. Let $N(P(1),P(2),...,P(n))$ be the number of these equivalence classes. Is $H(P(1),P(2),...,P(n))$ always non-empty? For which positive integers $n$ greater than 3, has the maximum possible value of $N(P(1),P(2),...,P(n))$ been computed-where the maximum is to be taken over all sets of n pairwise distinct co-planar points, no three of which are collinear?

What you call set $H$ is the set of simple polygonalizations of the $n$ points $P$. $H$ is only empty if all $n$ points are collinear. For one may form a star-shaped polygon by selecting a point $x$ in the convex hull, not in $P$ and not collinear with any two points of $P$, and connecting $P$ in angular order around $x$:
The maximum number (your $N$) of polygonizations of a $n$-point set $P$ is $c^n$ for $c$ somewhere between about $4.6$ and $56$.
• @GarabedGulbenkian: Just a crude upper bound. It is a very difficult problem to get an exact bound, tied up with the # of triangulations of a point set. Yes, there is an extension to $\mathbb{R}^3$ and higher dimensions, less explored. – Joseph O'Rourke Oct 14 '15 at 22:37