Convex Hull Algorithms
This video is about algorithms for computing the convex hull of points in 2D. Specifically, we consider the following algorithms:
a slow (cubic-time) algorithm,
Graham scan (O(n log n) time),
the giftwrapping algorithm (O(n*h) time, where h is the number of points on the hull), and
Chan's algorithm (O(n log h) time).
Next to talking about convex hull algorithms, this video also serves as a first introduction to geometric algorithm design.
We also made a Jupyter notebook with animations of these algorithms: https://nbviewer.org/github/Jerik79/g...
To interact with the notebook open it in Binder (the 3 rings at the top right corner).
00:00 introduction and definitions
03:28 the convex hull problem
07:15 designing geometric algorithms
09:43 slow algorithm
11:57 Graham scan
16:48 Graham scan: correctness
18:17 Graham scan: running time analysis
24:34 giftwrapping algorithm
26:54 giftwrapping: correctness
29:00 Chan's algorithm
37:05 Summary and Discussion