6
$\begingroup$

By making use of the fact that sorting $n$ numbers requires $\Omega(n \log n)$ steps for any optimal algorithm (which uses 'comparison' for sorting), how can I prove that finding the convex-hull of $n$ points is bounded by $\Omega (n \log n)$ steps?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ For your question see, en.wikipedia.org/wiki/… . A somehow surprising fact is that even if you choose some other model (like the quadratic decision model) the complexity is still bounded by $O(n\log{n})$ $\endgroup$ – Jernej Oct 29 '12 at 8:39
5
$\begingroup$

If you could create the convex-hull in $o(n \log n)$ time, this would imply, that you can sort $n$ numbers in $o(n\log n)$ time.

You do this with contradiction. You have $n$ numbers $(x_1, x_2, \ldots, x_n)$, which you would like to sort. From these numbers, you create points $P$ in 2D space in some fashion. For example $p_i=(x_i,x_i^2)$.

On these newly constructed points $P$ you call the algorithm for convex hull, which returns you the actual convex hull.

After that, you simultaneously traverse upper and lower hull, from the lower left-most point in (which you find in $O(n)$ time), to the upper right-most point. With this traversal you actually sort the numbers. Let $p_i$ and $p_j$ be the next points on lower and upper hull, then if $x_i<x_j$, you move one step ahead on the lower hull and add $x_i$ to the end of the sorted array (else you take one step ahead on the upper hull and add $x_j$ to the array). You then finish when the traversals meet in the upper right-most point of the convex hull.

The algorithm that I described is run in $O(n)$ time. So if the convex-hull algorithm would be $o(n\log n)$, the sorting of $n$ numbers could be also done in $o(n\log n)$ time, which is a contradiction since we know that sorting $n$ numbers takes at least $\Omega(n \log n)$ time.

|cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ I am not sure choosing points in this way is safe. Putting them on a parabola $p_i = (x_i,x_i^2)$ seems safer. $\endgroup$ – Jernej Oct 29 '12 at 8:34
  • $\begingroup$ Yes, I suppose you are right that this is safer. $\endgroup$ – Nejc Oct 29 '12 at 8:39
  • $\begingroup$ Odd... a problem with text formatting on stackoverflow. Everything was there, I just clicked edit and then save, and everything is here. :/ $\endgroup$ – Nejc Oct 29 '12 at 8:55
  • 1
    $\begingroup$ I straightened out your Landau symbols -- take care! Also, "The algorithm that I described is run in $O(n)$ time." is wrong; $o(n\log n) \neq O(n)$. The greater idea seems to work, though -- if you explain why the $\Omega(n\log n)$ bound applies to this setting. As far as I can see, the algorithm you construct is not (necessarily) a comparison sort. $\endgroup$ – Raphael♦ Oct 29 '12 at 18:57
  • 1
    $\begingroup$ @j_random_hacker infolab.stanford.edu/pub/cstr/reports/cs/tr/79/733/… $\endgroup$ – Aurélien Ooms Sep 20 '17 at 5:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.