# 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(ngn)$ 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.