Questions: Convex Hull Algorithms: Graham Scan and Gift Wrapping

Question 1

Using the cross product (b - a) x (c - a) = (bx - ax)(cy - ay) - (by - ay)(cx - ax), classify the turn from a = (0, 0) to b = (4, 0) to c = (2, 3).

• A. Counterclockwise (left) turn, because the value is positive
• B. Clockwise (right) turn, because the value is negative
• C. The points are collinear, because the value is zero
• D. The test cannot be applied, because c lies between a and b in x

Answer: (A)

(4 - 0)(3 - 0) - (0 - 0)(2 - 0) = 12 - 0 = 12, which is positive. A positive value means a counterclockwise, or left, turn at b. Graham scan keeps points that make left turns when walking the hull counterclockwise.

Question 2

For which input is Jarvis's march (gift wrapping) expected to be faster than Graham scan?

• A. A million points placed on a circle, all of them on the hull
• B. A million points: three that form a large triangle, and all the rest strictly inside it, so the hull has exactly 3 vertices
• C. Any input, because gift wrapping is always faster
• D. No input, because gift wrapping is always slower

Answer: (B)

Gift wrapping costs O(n) per hull vertex, O(nh) in total. With h = 3, that is linear time and beats the O(n log n) of Graham scan. With every point on the hull, h = n and gift wrapping takes O(n^2) time.

Question 3

In the algebraic decision tree model, a convex hull algorithm that outputs the hull vertices in order can run in O(n) worst-case time on arbitrary unsorted input.

• T. True
• F. False

Answer: False

Map numbers x1, ..., xn to points (xi, xi^2) on a parabola. Every point is on the hull, and the hull's vertex order is the sorted order of the numbers. Since sorting needs Omega(n log n) time in this model, so does computing an ordered hull.

Question 4

During Graham scan, the stack holds hull candidates. Explain what the algorithm does when the next point p makes a right turn with the top two points on the stack, and why.

Model answer: It pops the top point and checks again, repeating until the top two stack points and p make a left turn, and then pushes p. A right turn means the popped point lies inside or on the triangle formed by p0, the point below it on the stack, and p, so it cannot be a vertex of the convex hull.

Each point is pushed once and popped at most once, so the scan after sorting takes O(n) time. The O(n log n) sort dominates the total.