Give an O(n log n) convex hull algorithm and the orientation test it relies on, then prove that no comparison based algorithm can do better than Omega(n log n) by reducing sorting to convex hull.

Give an O(n log n) convex hull algorithm and the orientation test it relies on, then prove that no comparison based algorithm can do better than Omega(n log n) by reducing sorting to convex hull.

Approach: Build the hull as two monotone chains after sorting by x, using a cross product sign to pop non-convex turns. For the bound, map n numbers onto a curve where the hull order is the sorted order.

O(n log n) by the monotone chain algorithm, and Omega(n log n) is a lower bound. Sort the points by x then by y, sweep left to right maintaining a stack, and while the last three points make a non-left turn pop the middle one, then repeat right to left for the lower chain and concatenate. The turn test is the sign of the cross product (b - a) times (c - a) computed as (b.x - a.x)(c.y - a.y) - (b.y - a.y)(c.x - a.x), which is exact in integer arithmetic and is where a floating point implementation loses robustness on nearly collinear input. Each point is pushed once and popped at most once, so the sweep is O(n) and the sort dominates. For the lower bound, take n numbers x_1 to x_n and map each to the point (x_i, x_i^2) on a parabola. Every point is a vertex of the hull because the parabola is convex, and reading the hull in order returns the x values in sorted order, so a convex hull algorithm faster than n log n would sort faster than n log n, which the comparison lower bound forbids. The reduction from sorting costs O(n).

Follow-up: What does the output sensitive gift wrapping variant achieve when the hull has only h vertices, and when is it the better choice?

Key concepts: monotone chain, cross product, reduction from sorting, lower bound.