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?
Like this:
Like Loading...
Related
Things 
Think of it like this, a non self-intersecting curve is a one dimensional object(since it can be mapped in a one-to-one manner onto $\mathbf{R}$ whereas the plane is inherently two-dimensional.
Another way you could look at is(and this would appeal to people with a more physical bend of mind):
A curve is an “infinitesimal” part of a plane, just as a point can be thought of as an “infinitesimal” part of the real line. And, just as it takes an (uncountably)infinite number of points to cover the real line, it takes an uncountably infinite number of curves to cover the plane. Hence having such a curve is like reducing the job of finding needle in a haystack to picking out a needle from amongst a long line of toothpicks arranged end to end(in other words it represents a great deal of information).
Pardon the bad LaTeX: $\mathbf{R}$ ~ the real line.
Note that if the curve was allowed to self-intersect then that wouldn’t give a linear time algorithm. This is because given a set of points, a (not necessarily non)self-intersecting curve that passes through them all can be easily found in linear time. So the fact that helps bring down the runtime from
to linear is really that it is non self-intersecting, not just that it’s a curve.
Yeah, I know, in the case of self-intersecting curves every point cannot be mapped to one on the real line in a 1-1 fashion. One or more points will have more than one pre-image, and hence you don’t have a ‘function'(as in, the mapping isn’t) in the classical sense of the word, and most of your powerful tools of analysis(and perception) fail to apply. In other words a one-to-one(or rather any classical function) is much more ‘well-behaved’ than the mapping corresponding to a self-intersecting curve, in my opinion it is this “well-behaved-ness” that makes the problem easier to solve.