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?