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?

Advertisements

4 thoughts on “Curves

  1. Aftab Patel says:

    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).

  2. Vinayak says:

    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 O(n\log n) to linear is really that it is non self-intersecting, not just that it’s a curve.

    • Aftab Patel says:

      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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s