The algorithm for two-dimensional convex hulls uses sorting. Suppose someone gave you a library with convex hull implemented as a black box. Show how you would use the convex hull algorithm to sort a sequence of given integers. The phrase "black box" implies that you do not look inside the code; you only know what the input and output are and what the result looks like. You cannot "pull the sorting algorithm out" from the library implementation of convex hull. You can assume that you can call the convex hull algorithm as a primitive step.
3
votes
2 Answers
4
votes
For each xi from input sequence A=[x1,...,xn] of integers, n=|A|, create its corresponding point (xi, xi^2), then composing n points in the 2D space. Such points form a parabola which is a convex curve. In linear time you can inspect the points to detect the left most point pl, then you can traverse the convex hull starting from point pl to the right to produce the sorted order of the numbers x1,...,xn.
Because Ω(n logn) is the lower bound for comparison-based-sorting, we can argue that convex hull takes no less than that otherwise sorting could be done cheaper than its lower bound, which would lead to a contraction.
2
votes
Treat integers as points lying on x-axis (i.e. y-coordinate is zero). Feed the points to convex-hull algorithm. If the algorithm is not robust enough to handle this degenerate case, make each integer into two points (x, 1) and (x, -1). As output of the algorithm you will get the points that form closed loop (polygon). Go around and find the point with smallest x, after that the increasing x-values of points will represent the sorted integers.
Again, if the convex hull algorithm has problems dealing with border points lying on the same straight line, use squared integers for y-values to emphasize the convexity - this, of course, if all integers are non-negative. If there are negative integers, you need to subtract the minimum value before calculating squares for y-values.
