Скачать с ютуб Convex Hull Algorithms в хорошем качестве

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