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 nonempty? For which positive integers $n$ greater than 3, has the maximum possible value of $N(P(1),P(2),...,P(n))$ been computedwhere the maximum is to be taken over all sets of n pairwise distinct coplanar points, no three of which are collinear?
1 Answer
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 starshaped 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$.
^{ (Image from Erik Demaine's webpage.) }

$\begingroup$ Many thanks. That is a very nice way of getting a simple closed polygon through those n points. I wonder if it could be made to work in higher dimensional Euclidean spaces. I was also surprised ton learn that there is an actual formula for the maximum as a function of n. It looks like an asymptotic formula. Or is it just an upper bound. It is certainly an improvement on the crude upper bound n! $\endgroup$ Oct 14, 2015 at 22:34

$\begingroup$ @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. $\endgroup$ Oct 14, 2015 at 22:37