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?
6
$\begingroup$
$\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$
$\endgroup$
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.
-
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
