# Graham scan

tags
Algorithm

Graham scan is an algorithm to find the convex hull of a set of points in 2D. It runs with a time complexity of $$\mathcal{O}(n\log n)$$.

The algorithm is relatively simple. It starts by selecting the point with lowest $y$-coordinate. At each step of the algorithm, remaining points are sorted by increasing order of the angle they and the last added point make. Then, if this new point is

← Back to Notes