

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)$.

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.

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)$.

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.

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.

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!)