L12 - Convex Hull: Grahams Scan

Question 1

What is the worst case time complexity of Jarvis March?

Answer 1

O(N^2)

Question 2

Define the geometric property of Convex Hull that Grahams Scan is built on…

Answer 2

Convex hull can be traversed via making CCW turns

Question 3

What is the task specification for Grahams Scan? (Problem, input, output, input-output relation)

Answer 3

Problem: Find the convex hull of S points
Input: is a set of points in multi-dimensional space
Output: is a list of H convex hull points in CCW ordering.
Input-output relation: H is the smallest convex set in S.

Question 4

What was the motivation for Grahams Scan? When was it developed?

Answer 4

Grahams Scan was developed in 1972. The motive was to improve on the worst case time complexity of other convex hull algorithms such as Jarvis March. For example, Bell Labs were establishing hull for 10k points, and found the execution to be too slow.

Question 5

Explain the step by step process of the algorithm…

Answer 5

Start from the left most point, find next point with smallest polar angle, if the previous, current, and next point create a CCW turn, discard the current point from the stack.

Question 6

How are the points sorted?

Answer 6

Points are sorted via Polar angle

Question 7

What is the most computationally expensive step of the algorithm?

Answer 7

Sorting via polar angle is the most expensive step -> O(n log n)

Question 8

What is the worst case time complexity? Give proof…

Answer 8

Sort by polar angle + stack operations -> O(n log n) + O(n) = O( n log n )

Question 9

What is the polar angle of a point?

Answer 9

Polar angle is the CCW angle of a point from the X axis

Question 10

What is the improvement that Grahams Scan makes to Jarvis March?

Answer 10

Interior elimination, which ignores points known to not be on the convex hull.

Question 11

Give 3 applications of Convex Hull…

Answer 11

Robotics pathfinding, Classification (if hulls don’t overlap).