Convex Hull

A convex hull is the smallest convex polygon that contains all points of a given set.

Convex Hull Problem

how to find a convex hull?

Use Andrew’s Algorithm to construct the convex hull for a set of points in $O(n\log n)$ time.

The algorithm first locates the leftmost and rightmost points, and then constructs the convex hull in two parts: first the upper hull and then the lower hull.

Naive idea would be to connect two points to form a segment such that there are only points on one side of the the line.