Convex Hull

From Algorithmist
Jump to: navigation, search
This is a stub or unfinished. Contribute by editing me.

Computing the convex hull in Computational Geometry is what Sorting in many problems - it is perhaps the most basic, elementary function on a set of points.

Definitions[edit]

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[edit]

There are as many convex hull algorithms as Sorting algorithms. Any convex hull algorithm have the lower bound of \theta (n\log n) 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)
AlgorithmComplexity
Naive BruteforceO(n^{4})
Better BruteforceO(n^{3})
Gift Wrapping (Jarvis March)O(nh)
QuickHullO(nh)
Graham ScanO(n\log n)
Divide and ConquerO(n\log n)
Monotone ChainO(n\log n)
IncrementalO(n\log n)
Marriage before ConquestO(n\log h)
ShatterhullO(n\log h)
Chan'sO(n\log h)

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 O(nh) algorithms is O(n^{2}), and O(n\log n) for the O(n\log h) algorithms.

Summary of Convex Hull Algorithms[edit]

Naive Bruteforce[edit]

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 O(n^{3}) triangles for each of the O(n) points, this algorithm is O(n^{4}).

Better Bruteforce[edit]

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 O(n^{2}) edges, and each check requires going through the O(n) points, this algorithm is O(n^{3}).

Gift Wrapping[edit]

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 O(nh) time, or O(n^{2}) worst-case.

Divide and Conquer[edit]

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 O(n^{2}), or O(nh).

Graham Scan[edit]

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 O(n\log n), 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.