Quick Hull Worst case explanation

Question

What is the worst case for quick hull?? And how we can know that it is the worst case I am confused with quick hull algorithm. Actually, I understood, that running determinant to find the area of a triangle, and if the area is positive, then the point is on the left of the extreme points. And doing this thing recursively, will have O(n) efficiency for constructing a hull. Then I don't understood, that how to efficiency is sometimes mentioned O(nlogn) and )(n^2)? for which cases this efficiency turns out and how? please if someone can help by some particular example; that would be great help.

Answer 1

I'm afraid the accepted answer is not correct.

In fact, the case above is the O(n log n) case. Just look at the recursion tree. In each step you cut the set of points in two approximately equally large subsets. Therefore the height of the recursion tree is O(log n), resulting in an overall runtime of O(n log n).

To be more precise: The recurrence relation of the quickhull algorithm is T(n) = T(a * n) + T(b * n) + c*n. The last term (c*n) represents the search for the pivot element. In the case constructed above, the constants a and b are a = b = 1/2. You can use the master theorem to determine the bound of O(n log n).

The worst case O(n²) is a*n ≈ n-1 and b*n ≈ 1. You can construct it by placing points on the border of a circle using the following rule (in polar coordinates): P_i = (r, π / 2ⁱ). With this set of points the pivot element will always be the left-most point and therefore the set is divided into a subset containing n-1 points and an empty subset. So in each step of the recursion you only "eliminate" one point (the pivot element). The height of the recursion tree is therefore O(n) resulting in an overall efficiency of O(n²).

Answer 2

Here's an animated demo of John's answer, demonstrating how at each step, only one point is removed from consideration: