Graham’s scan Algorithm. An implementation in Rust.

Graham’s scan is a fantastic algorithm to find the convex hull of n given points in the plane. Moreover, it is one of the many algorithms that utilizes the data structure provided by a stack.

In one of my recent stories (here), I have explained an implementation of a stack in Rust. Now, let us apply this stack and at the same time learn about convex hulls and the aforementioned algorithm.

Convex hull:

Since we restrict ourselves in this story to points in a 2-dimensional plane, we can introduce these concepts quite visually.

A convex set is a set of points that contains for any two of its points a and b the points on the straight line connecting a and b.

One can show that for any set of given points, there exists a smallest convex set containing them. This leads to

The convex hull of a set of points is the smallest convex set that contains all these points.

Here, if we talk about ‘smallest’, then this is meant with respect to inclusion. So, a set a is smaller than b if all points of a are contained in b.

Algorithm:

Graham’s scan is an algorithm that determines the convex hull of n given points in O(n*log(n)). Its idea is very intuitive: