33.3 Finding the convex hull

33.3-1

Prove that in the procedure $\text{GRAHAM-SCAN}$, points $p_1$ and $p_m$ must be vertices of $\text{CH}(Q)$.

To see this, note that $p_1$ and $p_m$ are the points with the lowest and highest polar angle with respect to $p_0$. By symmetry, we may just show it for $p_1$ and we would also have it for $p_m$ just by reflecting the set of points across a vertical line.

To see a contradiction, suppose that we have the convex hull doesn't contain $p_1$. Then, let $p$ be the point in the convex hull that has the lowest polar angle with respect to $p_0$. If $p$ is on the line from $p_0$ to $p_1$, we could replace it with $p_1$ and have a convex hull, meaning we didn't start with a convex hull.

If we have that it is not on that line, then there is no way that the convex hull given contains $p_1$, also contradicting the fact that we had selected a convex hull

33.3-2

Consider a model of computation that supports addition, comparison, and multiplication and for which there is a lower bound of $\Omega(n\lg n)$ to sort $n$ numbers. Prove that $\Omega(n\lg n)$ is a lower bound for computing, in order, the vertices of the convex hull of a set of $n$ points in such a model.

Let our $n$ numbers be $a_1, a_2, \dots, a_n$ and $f$ be a strictly convex function, such as $e^x$. Let $p_i = (a_i, f(a_i))$. Compute the convex hull of $p_1, p_2, \dots, p_n$. Then every point is in the convex hull. We can recover the numbers themselves by looking at the $x$-coordinates of the points in the order returned by the convex-hull algorithm, which will necessarily be a cyclic shift of the numbers in increasing order, so we can recover the proper order in linear time.

In an algorithm such as $\text{GRAHAM-SCAN}$ which starts with the point with minimum $y$-coordinate, the order returned actually gives the numbers in increasing order.

33.3-3

Given a set of points $Q$, prove that the pair of points farthest from each other must be vertices of $\text{CH}(Q)$.

Suppose that $p$ and $q$ are the two furthest apart points. Also, to a contradiction, suppose, without loss of generality that $p$ is on the interior of the convex hull. Then, construct the circle whose center is $q$ and which has $p$ on the circle. Then, if we have that there are any vertices of the convex hull that are outside this circle, we could pick that vertex and $q$, they would have a higher distance than between $p$ and $q$. So, we know that all of the vertices of the convex hull lie inside the circle. This means that the sides of the convex hull consist of line segments that are contained within the circle. So, the only way that they could contain $p$, a point on the circle is if it was a vertex, but we suppsed that $p$ wasn't a vertex of the convex hull, giving us our contradiction.

33.3-4

For a given polygon $P$ and a point $q$ on its boundary, the shadow of $q$ is the set of points $r$ such that the segment $\overline{qr}$ is entirely on the boundary or in the interior of $P$. As Figure 33.10 illustrates, a polygon $P$ is star-shaped if there exists a point $p$ in the interior of $P$ that is in the shadow of every point on the boundary of $P$. The set of all such points $p$ is called the kernel of $P$. Given an $n$-vertex, star-shaped polygon $P$ specified by its vertices in counterclockwise order, show how to compute $\text{CH}(P)$ in $O(n)$ time.

We simply run $\text{GRAHAM-SCAN}$ but without sorting the points, so the runtime becomes $O(n)$. To prove this, we'll prove the following loop invariant: At the start of each iteration of the for loop of lines 7-10, stack $S$ consists of, from bottom to top, exactly the vertices of $\text{CH}(Q_{i - 1})$. The proof is quite similar to the proof of correctness. The invariant holds the first time we execute line 7 for the same reasons outline in the section. At the start of the $i$th iteration, $S$ contains $\text{CH}(Q_{i - 1})$. Let $p_j$ be the top point on $S$ after executing the while loop of lines 8-9, but before $p_i$ is pushed, and let pk be the point just below $p_j$ on $S$. At this point, $S$ contains $\text{CH}(Q_j)$ in counterclockwise order from bottom to top. Thus, when we push $p_i$, $S$ contains exactly the vertices of $\text{CH}(Q_j \cup \{p_i\})$.

We now show that this is the same set of points as $\text{CH}(Q_i)$. Let $p_t$ be any point that was popped from $S$ during iteration $i$ and $p_r$ be the point just below $p_t$ on stack $S$ at the time $p_t$ was popped. Let $p$ be a point in the kernel of $P$. Since the angle $\angle p_rp_tp_i$ makes a nonelft turn and $P$ is star shaped, $p_t$ must be in the interior or on the boundary of the triangle formed by $p_r$, $p_i$, and $p$. Thus, $p_t$ is not in the convex hull of $Q_i$, so we have $\text{CH}(Q_i - \{p_t\}) = \text{CH}(Q_i)$. Applying this equality repeatedly for each point removed from $S$ in the while loop of lines 8-9, we have $\text{CH}(Q_j \cup \{p_i\}) = \text{CH}(Q_i)$.

When the loop terminates, the loop invariant implies that $S$ consists of exactly the vertices of $\text{CH}(Q_m)$ in counterclockwise order, proving correctness.

33.3-5

In the on-line convex-hull problem, we are given the set $Q$ of $n$ points one point at a time. After receiving each point, we compute the convex hull of the points seen so far. Obviously, we could run Graham's scan once for each point, with a total running time of $O(n^2\lg n)$. Show how to solve the on-line convex-hull problem in a total of $O(n^2)$ time.

Suppose that we have a convex hull computed from the previous stage $\{q_0, q_1, \dots, q_m\}$, and we want to add a new vertex, $p$ in and keep track of how we should change the convex hull.

First, process the vertices in a clockwise manner, and look for the first time that we would have to make a non-left to get to $p$. This tells us where to start cutting vertices out of the convex hull. To find out the upper bound on the vertices that we need to cut out, turn around, start processing vertices in a clockwise manner and see the first time that we would need to make a non-right.

Then, we just remove the vertices that are in this set of vertices and replace the with $p$. There is one last case to consider, which is when we end up passing ourselves when we do our clockwise sweep.

Then we just remove no vertices and add $p$ in in between the two vertices that we had found in the two sweeps. Since for each vertex we add we are only considering each point in the previous step's convex hull twice, the runtime is $O(nh) = O(n^2)$ where h is the number of points in the convex hull.

33.3-6 $\star$

Show how to implement the incremental method for computing the convex hull of $n$ points so that it runs in $O(n\lg n)$ time.

(Omit!)