Algorithms for Convex Hull

For technical reasons, there is no recording from today's lecture. However, this folder contains the slides (weiyang-chen-spring-2020.pdf). In addition, I uploaded two optional reading materials , david-wu.pdf and insitu-tcs.pdf. In the former, the students at IN4330 can find the proof that Convex Hull and Sorting have equivalent asymptotic behaviour, and in the latter, Jyrki et al shows how Convex Hull can be computed in constant space.

Main takeaway

The important points are:

• The complexity of QuickHull (the algorithm which you are asked to implement in Oblig 4) is O(n^2).
• The optimal complexity is O(n lg n).
• Graham's scan is optimal.
• An efficient parallel algorithm will have to start by splitting the input into smaller chunks (since this will push the sorting part futher in).