Intuitively, if we think of each point in given set as being a nail sticking out from a board, the convex hull is the shape formed by a tight rubber band that surrounds all the nails.

Definition of Convex Hull

The convex hull of a set Q of points is the smallest convex polygon P for which each point in set Q is ether on the boundary of P or in its interior. We denote convex hull of Q as CH(Q).

CH(Q) = {p_o, p_1, p_3, p_10, p₁₂}

Lower Bound on Convex Hull

In order to established the lower bound for convex hull we reduce sorting problem into convex hull problem in the sense that convex hull algorithm can be used to solve sorting problem with little additional work. In other words, if we solve Hull problem quickly, we can solve sorting problem quickly.

Suppose, we are have an unsorted list of numbers to be sorted. <x₁, x₂, …, x_n>, x_i ≥ 0 for all i. Also, suppose we have an algorithm HULL that constructs the convex hull of n points in T(n) time. Our task is to use HULL to solve SORTING in time T(n) + O(n) where the O(n) represents additional time to convert the solution of HULL to the solution of SORTING.
Form the set of two-dimensional points (x_i, x_i²). These points lie on the parabola y = x². Run algorithm HULL to construct the hull. Clearly, every point is on the hull. Identify the lowest point a on the hull in O(n) time; this corresponds to the smallest x_i. The order in which the points occur on the hull counterclockwise from ‘a’ is their sorted order. Thus, we can use HULL algorithm to sort.

What we have showed that if we had a fast algorithm for the HULL, we could sort faster than O(n log n); but this is known to be impossible. This implies that the lower bound of convex hull is same as that of sorting and that is Ω(n log n).