Convex Hull

Introduction

The convex hull of a set of points is the smallest convex polygon that contains every point. A useful picture is a rubber band stretched around nails: after we release it, the band touches exactly the outermost nails.

Convex hull appears whenever only the boundary matters. It is used in geometry optimization, separating point sets, finding farthest pairs, and removing points that can never be extreme. By the end of this lecture, we will be able to construct the hull in $O(n \log n)$.

Problem or motivation

We are given $n$ distinct points. We need to print the vertices of their convex hull in counterclockwise order. Points that lie in the middle of a straight hull side will not be included; only the two endpoints of that side remain.

If there are one or two points, all of them belong to the hull.

Naive approach

An edge $(i,j)$ belongs to the boundary if every other point lies on the same side of its line. We can test all $$ pairs and scan all points for each pair, giving . This recognizes boundary lines, but ordering the result and handling collinear points also becomes awkward.