|This is a stub or unfinished. Contribute by editing me.|
A Convex Hull is the smallest convex polygon that contains every point of the set S. A polygon P is convex if and only if, for any two points A and B inside the polygon, the line segment AB is inside P.
One way to visualize a convex hull is to put a "rubber band" around all the points, and let it wrap as tight as it can. The resultant polygon is a convex hull.
Algorithms and Complexities
There are as many convex hull algorithms as Sorting algorithms. Any convex hull algorithm have the lower bound of through a reduction from Sorting, but it gives rises to Output Sensitive Algorithms, where the Complexity of the algorithm depends on the size of the output.
- n is the number of points
- h is the number of points in CH(S)
|Gift Wrapping (Jarvis March)|
|Divide and Conquer|
|Marriage before Conquest|
There are also other algorithms for special cases. Melkman's Convex Hull algorithm computes the convex hull of a simple polygonal chain (or a simple polygon) in linear time. Note that since h is at most n, the worst-case scenario for the algorithms is , and for the algorithms.
Summary of Convex Hull Algorithms
The bruteforce approach is use the definition. A point is on the convex hull if and only if it is not inside a triangle of any other three points. Since there are triangles for each of the points, this algorithm is .
Slightly better bruteforce is to realize that an edge is on the convex hull if and only if it is an extreme edge - all the other points lie on one side of it. Since there are edges, and each check requires going through the points, this algorithm is .
Gift Wrapping is perhaps the simplier of the convex hull algorithms. Starting from the lowest, left-most point (this point has to be on the hull), "gift wrap" by choosing the next point such that no points lie on the left of the line created by the current point and the next point. Repeat this until it wraps around back to the original point. The algorithm runs in time, or worst-case.
Divide and Conquer
Divide and Conquer and its resemblance to QuickSort is no mere coincidence - the concept is essentially the same. Recursively split the lists into two lists of a smaller size. Unforunately, the recurrence is the same, and thus the worst-case can be , or .
The Graham Scan algorithm has the optimal worst-case complexity when not taken account output-sensitivity. The basic concept is that we take an extreme point, sort all the other points angularly in , and scan angularly, with a stack in linear time to compute the convex hull. Since we sort in this algorithm, we are bounded by the output insensitive complexity.