Four Convex Hull Algorithms

Now I am taking COMP573 in HKUST. The title of the course is "Computational Geometry".

We are using the lecture notes written by Prof. David Mount, who are now visiting HKUST. One interesting fact is that the lecturer, Dr. Sunil Arya, is advised by Prof. Mount for PhD degree, while Prof. Mount is teaching an undergraduate algorithm course...

I think it is one of the few best lecture notes I have ever read.

In the lecture notes there are four algorithms to find the convex hull of a set of given points. They are Graham scan, Divide-and-Conquer Methodology, Quick Hull and Jarvis's March.

Another interesting fact I wanna mention here is that these 4 algorithms are analog (strongly or weakly) to insertiont sort, merge sort, quick sort and selection sort respectively.

Read Timothy Chan's algorithm, which combines Graham scan and Jarvis March to form a quicker output sensitive algorithm. The idea is indeed very simple; but this is real intelligence.