Given a point set, , the convex hull, , is a convex polygon such that comprises a subset of arranged in a clockwise order and that all points in are included in or on the edge of the polygon.
(1) The algorithm shown below computes from a given . Show the complexity of line 4-7 in the notation. Explain the reason. Arithmetic operations over real numbers have infinite precision and can be computed in a unit time. returns true only if and turns clockwise (i.e., the cross product is negative).
1. Let $s$ be an empty stack. We denote by $s_i$ the $i$-th element from top of $s$. 2. Take the bottommost point of the leftmost points in $P$, and let it be $\mathbf{v_s}$. 3. Leave out $\mathbf{v_s}$ of $P$, sort in order of the slope of the line from $\mathbf{v_s}$ to $\mathbf{v_i}$. Let the result be $P'$ 4. for $\mathbf{v}$ in $P'$: 5. while the size of $s > 1$ and not $\mathrm{cw}(s_2, s_1, v)$: 6. pop an element from $s$ 7. push $\mathbf{v}$ to $s$
(2) Suppose is given. Let , and we computed the convex hull for . Given , prove that the sorted array of can be computed in linear time in terms of .
(3) Prove that the complexity of an algorithm that computes the convex hull of points (not necessarily the algorithm shown in (1)) is not smaller than the complexity of a sorting algorithm for elements.
(4) Suppose we use a random function that returns true/false at 50% of probability, respectively. Prove that we need to call at least times to output one of all possible permutations of integers from 1 to with the equal probability.
(5) Consider a computation model where the sorting algorithm with the smallest complexity is based on comparison between two numbers. Prove that the complexity of computing a convex hull is intrinsically . Use the Stirling’s approximation formula, , if need be.
To analyze the complexity of lines 4-7, we note that the primary operation in the for loop is the while loop which pops elements from the stack and then pushes the current point . The key observation is that each point is pushed and popped from the stack at most once.
Push Operation: Each point is pushed exactly once.
Pop Operation: Each point is popped at most once.
Therefore, the total number of operations in the while loop is . Hence, the complexity of lines 4-7 is .
To prove: The sorted array of can be computed in linear time given .
Observe the relationship between and :
Each point in is of the form
This forms a parabola in the 2D plane
Key insight:
The convex hull captures the "outer" points of this parabola
These outer points correspond to the smallest and largest elements of
Properties of the convex hull :
It consists of an upper hull and a lower hull
The leftmost and rightmost points of correspond to the minimum and maximum elements of respectively
Algorithm to sort using :
a) Identify the leftmost point of . This gives the minimum of .
b) Identify the rightmost point of . This gives the maximum of .
c) Traverse the upper hull of from left to right.
Each point encountered gives the next element in the sorted .
Time complexity analysis:
Finding the leftmost and rightmost points of :
Traversing the upper hull of :
Total time complexity:
Correctness:
The upper hull of contains all points that are not "hidden" by other points when viewed from above
These points, when projected onto the x-axis, give the sorted order of
Therefore, given the convex hull , we can indeed sort in linear time .
(3) Complexity of computing convex hull vs. sorting
Let's assume we have an algorithm that can compute the convex hull of points faster than any comparison-based sorting algorithm. We will show that this leads to a contradiction by leveraging the known lower bound of comparison-based sorting algorithms.
Consider a set of distinct real numbers that we want to sort. Transform these numbers into a set of points .
All points in lie on a straight line (the -axis). The convex hull of these collinear points will consist of exactly two points: the leftmost point and the rightmost point. The leftmost point corresponds to the minimum value in our original set, and the rightmost point corresponds to the maximum value.
Assume algorithm computes the convex hull faster than any comparison-based sorting algorithm. Then we could:
Treat our numbers as points.
Compute the convex hull with .
Convert the sorted points back to numbers in order.
Thus, we would have a way to sort the elements as quickly as , which contradicts to our assumption that algorithm computes the convex hull faster than any comparison-based sorting algorithm.
Therefore, we prove that the complexity of computing the convex hull of points cannot be smaller than the complexity of sorting elements in the general case.
(4) Number of calls to r() for random permutations
The number of permutations of integers is .
To represent different outcomes (permutations) uniformly, we need at least bits of information, as this is the minimum number of bits required to encode distinct values.
Each call to r() generates one bit of information.
Therefore, to generate a random permutation uniformly, we need at least bits, and hence we need to call r() at least times.
To prove all possible permutations of integers from 1 to has the equal probability to be generated by r(n) for times, we can number all the permutations from 0 to and use the binary representation of the numbers to determine the permutation.
Since r() generates a random bit with equal probability, the binary representation of the numbers will be uniformly distributed, and thus all permutations will have an equal probability of being generated.
(5) Convex hull complexity using comparison model
Sorting based on comparison between 2 numbers can be viewed as constructing a decision tree where each comparison narrows down the possible orderings. The height of this tree represents the number of comparisons needed, which is in the worst case.
Using Stirling's approximation formula , we have:
So sorting elements requires comparisons in the comparison model.
To show that the complexity of computing the convex hull is intrinsically , we can consider both the lower bound and the upper bound of the complexity:
Lower bound:
Based on the conclusion in (3), the complexity of computing the convex hull is not smaller than the complexity of sorting elements, so the lower bound of the complexity of computing the convex hull is .
Upper bound:
Based on the algorithm given in (1), computing the convex hull consists of sorting the points based on the slope of the line from the leftmost point, which can be done in time, and construct the convex hull in time using a stack, which can be done in time based on the analysis in (1). Therefore, the upper bound of the complexity of computing the convex hull is .
Hence, the complexity of computing the convex hull is intrinsically .