\input CS445Hdr
% This is CS445N4.tex of January 18, 1982 9:47 PM

\def\title{Lecture 4}
\def\header{4. Convex hull algorithms}
\chap{\header.}
\sect{4.1}{Jarvis’ algorithm.}

In this section we will present a simple algorithm for finding the convex hull of $n$ points in the plane. It is due to R. A. Jarvis (1973), and assumes that at least two of the points are distinct:\par

\algorithm{4.1}{Convex hull of a set of point $P$ in the plane.}{
\step 1. [Find an extremal point.]{Let $p0̌$ be the point of $P$ with minimum $y$-coordinate, and let $\lscr$ be the horizontal line passing through $p$ and oriented to the left. Set $p\gets p0̌$, $H\gets \emptyset$}
\step 2. [Rotate the supporting line.]{Set $H\gets H \uni\leftset p\rightset$, $P\gets P-\leftset p \rightset$. Among all points of $P$, select the point $q$ for which the angle between $\lscr$ and segment $pq$ is smallest.}
\step 3. [Test for termination.]{If $q=p0̌$, return $H$ and stop. Otherwise set $p\gets q$ and go back to step 2.}}

If we take $d$ to be perpendicular to $\lscr$ (and pointing down in step 1), we can see that this algorithm is implementing a ``walk’’ along the direction circle. Step 1 enters the circle at its lowest point; step 2 determines the endpoint of arc $Ip̌$ and jumps to it.\par

The time required by this algorithm is $O(nh)$, where $h$ is the number of points in the convex hull (the number of times step 2 is executed). In the worst case, we may have $h=n$, giving a total time bound of $O(n↑2)$. The average case is usually better: as we will see later on, if the points are randomly distributed inside a polygon with fixed number of sides, the expected value of $h$ is $O(\log n)$. We will also see that $O(n \log n)$ is a lower bound for the complexity of finding the convex hull of $n$ points, so Jarvis’ algorithm is not that bad.

The inner loop of algorithm 4.1 is the comparision of two vectors $u=q\pr-p$ and $v=q\prr-p$ to see which makes the smallest angle with the line $\lscr$. Since it is known beforehand that $q\pr$ and $q\prr$ are both on the same side of $\lscr$, we have $(\angle\lscr v)-(\angle\lscr u) = \angle uv\in [-\pi, \pi]$, and therefore $\sign\angle uv=\sign \sin\angle uv$.\fig4
Therefore, the angles can be compared by checking the sign of the vector product $$u\times v=\leftv u\rightv\leftv v\rightv\sin \angle uv=xǔyv̌-xv̌yǔ,$$ and this requires just two multiplications and one addition.

If ties occur in step 2 ($u\times v=0$, i.e. $p$, $q\pr$ and $q\prr$ are colinear), one should retain the the point $q$ that is farthest from $p$, in order to guarantee that the next arc $Iq̌$ is not a single point. This precaution also has the effect of ensuring $\angle uv\neq\pm\pi$ in the following iterations of step 2, and thus removing the ambiguity of the case $u\times v=0$. If this precaution is not taken, the algorithm may fail.

This algorithm may be said to use the ``rope fence’’ method, in which a rope (the line $\lscr$) is strung around a collection of poles (the points of $P$). This analogy helps in understanding the ``gift wrap’’ method, the generalization of Jarvis’ algorithm to 3 dimensions, where $P$ is placed on a sheet of paper (a supporting plane) and this is folded up repeatedly so as to enclose $P$ as tightly as possible.

???R. L. Grahams (1972)