Graham Scan Algorithm Tutorial

In this video we’ll learn about the Graham Scan, an algorithm developed in the 70s, used to construct ‘Convex Hulls’. Before we delve into the details of the algorithm, we’ll first learn a bit on ‘Convex Hulls’ themselves, and some ways of testing to see if a set of points constitutes a ‘Convex Hull’. Towards the middle of the lesson, we’ll switch over to our coding editor and actually implement the algorithm in Python (2.7).

https://www.youtube.com/watch?v=vPDPE66nhlo

Code for this lesson

https://github.com/bfaure/Python_Algorithms/blob/master/graham_scan/main.py

References

[1] https://en.wikipedia.org/wiki/Convex_hull_algorithms
[2] https://en.wikipedia.org/wiki/Convex_hull
[3] https://www.youtube.com/watch?v=0HZaRu5IupM
[4] http://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/
[5] https://en.wikipedia.org/wiki/Graham_scan

End song is “Out of the Skies Under the Earth” by Chris Zabriskie