CS2303 Tutorial Week 3 Notes (Optional):
Problem: Design an algorithm to compute convex hull for a set of points
Definition of Convex Hull: The minimum convex polygon that can contain all the given points.
Example:
Computing the convex hull is equivalent to deciding which points are on the boundary of the convex hull (Imagine the points as nails and then put an elastic string around them)
Fact: the leftmost point O must be on the convex hull.
Method: Scan the points by the order of the angle decided by the line connecting them to O and the horizontal line. Gradually adjust the outer contour to the one we needed.
O
Think about the solution by yourself (You can try some simple examples first)
Solution:
We have four algorithms: Gift Wrapping, Quick Hull, Merge Hull, and Graham Scan
For Graham Scan, we sort all the points other than O according to the slopes of the lines connecting them and the point O (leftmost point).
Below is the table summarizing the number of pushes and pops during the process of scanning.
Pop Push
1 0 1
2 0 1
3 2 <=3
4 t4 <=3
5 t5 <=3
…
N tN <=3
We know that if k points are popped, then k-2 points are removed from the stack. However, each point can only be removed once. Therefore, we have t4-2+t5-2+…+tN-2<=N, which implies t4+t5+…+tN<3N. The number of pushes in total is also less than 3N. Hence, the total number of push and pop in the whole process is at most 6N, which is linear in input size.