Member-only story
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
andb
the points on the straight line connectinga
andb
.
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: