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

{{< img src="/img/grahamscan.gif" title=“Graham scan algorithm demo” width=200 alt=“Graham scan demo” class=“center” >}}

Comments


← Back to Notes