If you have been given a bunch of points on a plane, finding the convex hull takes 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 factor from the run-time of an algorithm. What are some other places where this information helps?