Places where the order of points along a simple polygon passing through them is useful

Question

We know that finding the convex hull of $n$ points on a plane has a lower bound of $\Omega(n\log n)$ on its running time. However, if the points are given in the order in which they occur along some simple polygon that has those points as its vertices, then their convex hull can be found in linear time.

I find this intriguing because there are probably too many simple polygons that have the given points as their vertices and therefore, intuitively, the order along one of them sounds like a very useless piece of information. And yet, it helps.

So my question is, are there other places where the same information helps in bringing down the running time of an algorithm?

As a side, I also want to know bounds on the number of permutations of a given set of points on a plane for which there is a simple polygon with those points as its vertices so that the order in which the points occur along the polygon is the same as the order in the permutation. What's known about this?

Answer 1

Your comment that "there are probably too many simple polygons" is the key, because actually there aren't that many. $n$ points have $n!$ paths (permutations) and $(n-1)!/2$ polygons if we allow self intersections -- that is, $2^{\Theta(n \log n)}$.

The numbers of paths or polygons without self intersections are $2^{\Theta(n)}$, easiest observed from the fact such paths and polygons can be completed to triangulations, the number of triangulations of a given point set in the plane is $<30^n$ [Sharir-Sheffer'09, latest in a long history], and the number of proper subsets of edges of each triangulation is $<2^{3n-6}$.

The convex hull of simple polygons has been one of my favorite things since using it to find and/or formulae for polygons in SIGGRAPH'88 http://dx.doi.org/10.1145/54852.378472