Lower bound for Convex hull
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&lt;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.