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?


1 Answer 1


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$.
          (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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.