Curves

If you have been given a bunch of points on a plane, finding the convex hull takes \Omega(n\log n) time. However, if you have been given, in addition, a non self-intersecting curve passing through all the points and the order in which the points occur along the curve, then the convex hull can be found in linear time. I find it a bit surprising that a non self-intersecting curve passing through all the points actually contains sufficient information to remove the \log n factor from the run-time of an algorithm. What are some other places where this information helps?