\input CS445Hdr
% This is CS445N4B of February 9, 1982  12:00 AM
\setcount0 20
\def\header{4. Convex hull algorithms}
\def\title{Lecture 8}

\sect{4.6. Analysis of ``split and merge'' algorithms.}

In the previous sections, we discussed two recursive algorithms for finding
convex hull (4.3 and 4.4) that could be described as using the
``split-and-merge'' method. The running time $H(n)$ of such
algorithms is given by the following general recurrence:
$$H(n)\leq\alter{$O(1)$|if $n=1$,\cr\vb
$H(\alpha n)+H(\beta n) +S(n)+M(n)$| otherwise\cr}\eqno(1)$$
where $S(n)$ is the time required to split a problem of size $n$ in
two subproblems whose sizes are at most $\alpha n$ and $\beta n$,
and  $M(n)$ is how long it takes to merge the two solutions.
The formula above holds
both for maximum (worst-case) and for average times.\par

Recurrence (1) is extremely common in the analysis of combinatorial
algorithms. The asymptotic behavior of $H(n)$ depends on
that of $S(n)+M(n)$, and on the
constants $\alpha$ and $\beta$. Some of the most common
cases are summarized in the table below:
$$\vbox{\tabskip0pt
\halign{\ctr{\hskip10pt #}|\ctr{\hskip10pt #}|\ctr{\hskip10pt #}\cr
$\alpha+\beta$ | $S(n)+M(n)$ |$H(n)$\cr
\noalign{\vskip6pt\hrule\vskip6pt}
$\null\leq 1$|$O(n)$|$O(n\log n)$\cr\vb
$\null\leq 1$|$O(n^p)$, $p<1$|$O(n)$\cr\vb
$\null\leq c< 1$|$O(n)$|$O(n)$\cr\vb
$\null\leq 1$|$\dispstyle O\biglp{n\over{\log n}}\bigrp$|
$O(n\log\log n)$\cr\vb
$\null\leq 1$|$\dispstyle O\biglp{n\over{(\log n)^p}}\bigrp$,
$p>1$|$O(n)$\cr}}\eqno(2)$$

For example, in algorithm 4.3 (Preparata-Hong) the split and merge
operations took $O(n)$ time, and $\alpha=\beta={1\over2}$\foot1{This is
not exactly true, since $\lceil n/2\rceil$ can be as large as ${2n\over3}$.
When $n$ is not a power of 2, we need a more general version of
recurrence (1), namely\ftpar
\null\ftfill$\dispstyle H(n)\leq H(\alpha
n n)+H(\beta
n n) + S(n)+M(n)$
\ftpar where $\alpha
n$ and $\beta
n$ are allowed to depend on $n$.
Table (2) remains valid in this general formulation, as long as we have
$\alpha
n\leq \delta$ and $\beta
n\leq \delta$ for
some constant $\delta$ strictly less than 1.}, so
the total running time is $O(n\log n)$. The same is true of
algorithm 4.4 (Shamos-Houy). In the latter, the split operation
requires a preliminary sorting step, so the bound is tight:
we require $\Theta(n\log n)$ time\foot2{We say $f(n)=\Omega(g(n))$
iff we have $\leftv f(n)\rightv\geq cg(n)$ for some positive
constant $c$ and all sufficiently large $n$. We say that
$f(n)=\Theta(g(n))$ iff $f(n)=O(g(n))$ and $f(n)=\Omega(g(n))$, i.e.
we have $c
1g(n)\leq\leftv f(n) \rightv \leq c
2g(n)$ for some
positive constants $c
1, c
2$ and for all sufficiently large $n$.}.\par

Actually, in both algorithms the merge operation requires only
$O(h
1+h
1)$ operations, where $h
1$ and $h
2$ are the 
number of vertices in the hulls of the two subproblems.
In the worst case, we may have $h
1+h
2=n$; however,
the {\it average} value of this quantity grows much slower
than $n$, as we shall see.\par

We already remarked that for algorithm 4.3 the statistical distribuition
of the points in the two subproblems is the same as in the original one.
If we let $\bar h(n)$ be the average number of vertices on the
convex hull of $n$ random points of the plane, then the average merge
time for algorithm 4.3 will be
$$O\left(\bar h\biglp\lceil {n\over 2}\rceil\bigrp+
\bar h\biglp\lfloor{n\over 2}\rfloor\bigrp\right)=O\left(\bar h(n)\right),$$
and the split time is $O(1)$.\par

We should note that the function $\bar h(n)$ is relevent also in the analysis
of Jarvis' algorithm (4.1): as we saw, its running time is $O(nh)$, where
$h$ is the size of the resulting hull. The asymptotic behavior of
$\bar h(n)$ is therefore worth of a more detailed analysis.\par

\sect{4.7. Random points in a triangle.}

In this section we will analyze the behavior of $\bar h(n)$
for a very simple case: we will assume the $n$ given points
are uniformly distributed inside a triangular region of the plane.
Moreover, we will henceforth assume that the
points are independent of each other.\par

There are several obvious ways to tackle the analysis of $\bar h(n)$.
For example, we might try to use some ``divide and conquer'' method
(like that used in algorithm 4.3) to get a recurrence relation
for $\bar h(n)$. We could also try to compute the probability that one point
falls inside the triangle defined by three others, or that the $(i+1)$-th
point falls inside the hull of the preceding $i$ ones, and somehow use
this result to get the average number of vertices in the hull.\par

Unfortunately, these ideas generally translate into rather messy
statistical formulas, which are very hard to evaluate.
The approach we will follow in this section
is the one used by A. R\'enyi and R. Sulanke (1963) to prove
the result below:

\theorem{4.4}{The convex hull of a set $P$ constituted of
$n$ random points uniformly and independently distributed in
an arbitrary triangle $T$ has, on the average, 
$$\eqalign{\bar h(n)|=2H
{n-1}\cr\vb
     \null|=2(1+{1\over2}+{1\over3}+\cdots+{1\over {n-1}})\cr\vb
     \null|=2(\ln n+\gamma+o(1))\cr}$$
vertices.}

\proof{Note that the number of edges on the convex hull is equal to the
number of vertices, and that each edge is determined by two of the given
points. Therefore, $\bar h(n)$ is also the average number of pairs
$p
i, p
j\in P$ such that segment $p
ip
j$ is an
edge of the hull. If we define the random variables
$$\epsilon
{ij}=\alter{
   1|if $p
ip
j$is an edge of $\hull(P)$,\cr\va
   0|otherwise.\cr}\eqno{(3)}$$
then the number of edges (vertices) of $\hull(P)$ will be
$$\sum
{1\leq i<j\leq n}\epsilon
{ij},$$
and therefore
$$\bar h(n)=\sum
{1\leq i<j\leq n}\Pr(\epsilon
{ij}=1).\eqno{(4)}$$
Since all points have the same distribution, $\Pr(\epsilon
{ij}=1)$
is a constant. To compute sum (4), all we need to know is 
one of its terms, say $\Pr(\epsilon
{12}=1)$.\par

\def\dint#1{\int\<\int\limitswitch
{#1}}
\def\vint{\int\limitswitch}

\hp Since the probability of getting three collinear points is zero,
$\Pr(\epsilon
{12}=1)$ is also the probability that the line through 
$p
1$ and $p
2$ is a supporting line of $P$, i.e. that all other points
fall on the same side of it. If we let $F\pr$ and $F\prr$ be the areas of
the two parts in which this line divides the triangle $T$, and
$F=F\pr+F\prr$ be the total area, then
$$\eqalignno{\Pr(\epsilon
{12}=1)|=\dint{R}\Pr(p
1)\Pr(p
2)
    \left(\left({F\pr\over F}\right)^{n-2}+
    \left({F\prr\over F}\right)^{n-2}\right)\,dp
1\,dp
2\cr\vb
              \null|={1\over{F^2}}\dint{R}
    \left(\left({F\pr\over F}\right)^{n-2}+
    \left({F\prr\over F}\right)^{n-2}\right)\,dp
1\,dp
2|(5)\cr}$$
where $R$ is the set of all pairs of points $(p
1, p
2)$
belonging to the given triangle\foot1{
Note that each integral is actually a double one, .i.e.
\hskip0pt plus 1000pt\null\penalty-1000\null\hfill$\dispstyle\dint{\null} f(p, q)\,dp\,dq=
\int\int\int\int f(x
p, y
p, x
q, y
q)\,dx
p\,dy
p\,dx
q\,dy
q$
\null\hfill}.\par

\hp Let $a$, $b$ and $c$ be the vertices of $T$.
The line defined by each pair $(p
1, p
2)\in R$ intercepts exactly
two sides of $T$ (again, the probability of it passing through
one of the vertices is zero). We classify the pair $(p
1, p
2)$ as
belonging to one of three subsets $R
a$, $R
b$ and $R
c$ of $R$,
depending on whether those two sides meet at $a$, $b$ or $c$. Integral
(5) can be decomposed in three parts, $I
a$, $I
b$, and $I
c$, where
$$I
a={1\over{F^2}}\dint{R
a}\left(\left({F\pr\over F}\right)^{n-2}+
    \left(1-{F\pr\over F}\right)^{n-2}\right)\,dp
1\,dp
2,\eqno{(6)}$$
and similarly for $I
b$ and $I
c$.\par

\hp Since the integrand of (5) is symmetric in $F\pr$
and $F\prr$, we can assume
in (6) that $F\pr$ is the part of the triangle that contains vertex $a$,
and similarly for $I
b$ and $I
c$. Note that the area $F\pr$
(and hence the integrand) in $I
a$ is
completely determined by the distances $u$ and
$v$ from vertex $a$ to the points $b\pr$ and $c\pr$
where the line $p
1p
2$
meets sides $\seg{ab}$ and $\seg{ac}$;\fig4
in fact,
$F\pr={1\over 2}uv\sin \alpha$, where $\alpha$ is the angle at $a$.\par

\hp To compute $I
a$, we will perform a
change of variables, replacing $p
1$ and $p
2$ by the distances $u$ and $v$.
This requires that we rewrite the differential $dp
1\,dp
2$ in terms of
$u$, $v$, $du$ and $dv$.\par

\hp Consider therefore the integral
$$\dint{R
a\pr(u,v)}\,dp
1\,dp
2\eqno(7)$$
where $R
a\pr(u,v)$ is the set of all point pairs $p
1,p
2$ in $R
a$ for
which the line $p
1p
2$ crosses the segments $ab\pr$ and $ac\pr$. 
To evaluate this integral, consider that for each choice of point
$p
1$, the point $p
2$ must be eiter in region I or in region IV of the figure below,\fig4
otherwise the line $p
1p
2$ will not meet the sides of $T$ at the
required places.
A trivial but tedious computation shows that the average area of
each of the six regions I--VI, when $p
1$ ranges over the whole
triangle $ab\pr c\pr$, is one-sixth of the area of the latter ($F\pr$)\foot1{
Another way to arrive at this conclusion is to prove it by a symmetry
argument in the case of an equilateral triangle, and then extend
the result to arbitrary triangles by using the properties of affine
transforms. This technique is rather common in the study of
convex figures; we will have the occasion to use it again later in
this chapter.}. Since this area is ${1\over 2}uv\sin\alpha$,
formula (7) evaluates to
$$\eqalignno{\dint{T(u,v)}\,dp
1\,dp
2|=
   \left({{uv\sin \alpha}\over 2}\right)
   \left({2\over 6}\,\cdot\, {{uv\sin \alpha}\over 2}\right)\cr\vb
\null|=
   {{u^2v^2(\sin \alpha)^2}\over 12}.|(8)\cr}$$
Computing the differentials of both sides
with respect to $u$ and $v$ gives
$$dp
1\,dp
2={{uv\,(\sin\alpha)^2\,du\,dv}\over 3}$$
Since the area $F\pr$ of the piece containing $a$ is 
${1\over 2}uv\sin\alpha$, we have
$$I
a={1\over{F^2}}\vint
0^{\seg{ab}}\vint
0^{\seg{ac}}
    \left(\left({{u v\sin \alpha}\over{2F}}\right)^{n-2}+
          \left(1-{{u v\sin \alpha}\over{2F}}\right)^{n-2}\right)\,
    {{uv\,(\sin \alpha)^2}\over 3}\,dv\,du.\eqno(9)$$\par

\hp By a second change of variables
$$X=u\sqrt{{\sin\alpha}\over{2F}}\qquad\hbox{and}\qquad
  Y=v\sqrt{{\sin\alpha}\over{2F}}$$
we get 
$$\eqalignno{I
a|=
      {1\over{F^2}}\vint
0^B \vint
0^C
       \biglp (XY)^{n-2}+(1-XY)^{n-2}\bigrp{1\over 3}
        {{XY}\over{\dispstyle{\sin\alpha}\over{2F}}}
        (\sin \alpha)^2
        {{dY\,dX}\over{\dispstyle{\sin\alpha}\over{2F}}}\cr\vb
    \null|={4\over 3}\vint
0^B\vint
0^C
       \biglp (XY)^{n-2}+(1-XY)^{n-2}\bigrp XY\,dY\,dX|(10)\cr}$$
where
$$B=\seg{ab}\sqrt{{\sin\alpha}\over{2F}}
  \quad\quad\hbox{and}\quad\quad
  C=\seg{ac}\sqrt{{\sin\alpha}\over{2F}}.$$\par

The evaluation of (10) presents no great problems. We have
$$\eqalignno{\vint
0^B\vint
0^C (XY)^{n-2}XY\,dY\,dX
  |=\bigglp\vint
0^BX^{n-1}\,dX\biggrp
      \bigglp\vint
0^CY^{n-1}\,dY\biggrp\cr\vc
\null|={(BC)^n\over {n^2}},|(11)\cr}$$
and, since $BC=({1\over 2}\seg{ab}\;\seg{ac}\sin\alpha)/F=1$, we get
$$\vint
0^B\vint
0^C (XY)^{n-2}XY\,dY\,dX={1\over {n^2}}.
\eqno(12)$$\par

\hp We also have
$$\eqalignno{\vint
0^B\vint
0^C (1-XY)^{n-2}XY\,dY\,dX
   |=\vint
0^B\vint
0^C \biglp(1-XY)^{n-2}-(1-XY)^{n-1}\bigrp
         \,dY\,dX\cr\vb
\null|=\vint
0^C\vint
0^B (1-XY)^{n-2}\,dX\,dY\cr\vb
\null|\quad\quad\quad - \vint
0^C\vint
0^B (1-XY)^{n-1}\,dX\,dY.|(13)\cr}.$$\par

By substituting $Z$ for $1-XY$, the second integral above becomes
$$\eqalignno{\vint
0^C\vint
0^B (1-XY)^{n-1}\,dX\,dY
      |=-\vint
0^C {1\over Y}
       \left(\vint
1^{1-BY} Z^{n-1}\,dZ\right)\,dY\cr\vb
\null|=\vint
0^C {1\over Y}\left({{1 - (1-BY)^n}
       \over n}\right)\,dY\cr\vb
\null|={1\over n}\vint
0^C {{1 - {(1-BY)^n}}
       \over {Y}}\,dY.|(14)\cr}.$$
Substituting $W$ for $(1-BY)$, we get
$$\eqalignno{\vint
0^C\vint
0^B (1-XY)^{n-1}\,dX\,dY
   |=-{1\over n}\vint
1^{1-BC} {{1 - W^n}\over {1-W}}\,dW\cr\vb
\null   |=-{1\over n}\vint
1^0 (1+W + W^2 +\cdots
           + W^{n-1})\,dW\cr\vb
\null|={1\over n}\left[W + {W^2\over 2} + {W^3\over 3} +
    \cdots + {W^n\over n}\right]
0^1\cr\vb
\null|={1\over n}\bigglp 1 + {1\over 2}+ {1\over 3}+\cdots
      + {1\over n}\biggrp|(15)\cr}.$$
and therefore
$$\vint
0^C\vint
0^B (1-XY)^{n-2}\,dX\,dY
   ={1\over {n-1}}\bigglp 1 + {1\over 2}+ {1\over 3}+\cdots
      + {1\over {n-1}}\biggrp\eqno(16)$$\par

\hp From (10)-(16) we get
$$\eqalignno{I
a\quad
    |=\quad{4\over 3}\left[{1\over {n^2}}
      +{1\over {n-1}}\bigglp 1 +
              {1\over 2}+ {1\over 3}+\cdots
      + {1\over {n-1}}\biggrp\right.\cr\va
\null|\quad\quad\quad\quad\left.\null - {1\over n}\bigglp 1 +
               {1\over 2}+ {1\over 3}+\cdots
      + {1\over n}\biggrp\right]\cr\vb
\null|=\quad{4\over 3}\left({1\over {n^2}}
      +{{\dispstyle 1+{1\over 2}+ {1\over 3}+\cdots
      + {1\over {n-1}}}\over{n(n-1)}} - {1\over {n^2}}\right)\cr\vb
\null|=\quad{2\over 3}{n\choose 2}^{-1}\left(1+{1\over 2}+ {1\over 3}+\cdots
      + {1\over {n-1}}\right)\cr\vb
\null|=\quad{2\over 3}{n\choose 2}^{-1}H
{n-1}.|(17)\cr}$$\par

\hp Since this integral does not depend on $\alpha$, $\seg{ab}$, or
$\seg{ac}$, we must have $I
b=I
c=I
a$; therefore
$$\Pr(\epsilon
{12}=1)=I
a+I
b+I
c=2{n\choose 2}^{-1}H
{n-1},\eqno(18)$$
and
$$\eqalign{\bar h(n)|=\sum
{1\leq i<j\leq n}\Pr(\epsilon
{ij}=1)\cr\vb
\null|=\quad{n\choose 2}\Pr(\epsilon
{12}=1)\cr\vc
\null|=\quad2H
{n-1}\cr}.$$}

The above theorem may be somewhat surprising, since it says that
the value of $\bar h(n)$ is completely independent of the
size and shape of the triangle $abc$.  But this conclusion could have
been reached beforehand, by using a few elementary facts about
affine transforms.\par

An affine transform can be defined as a
linear transformation followed by a parallel displacement; so,
in the plane,
a point $(x,y)$ is mapped to $(ax+by+c, dx+cy+e)$ where
$a$--$e$ are constant parameters of the transform. It
can be shown without much trouble
that affine transforms preserve ``inside-outside'' relationships,
map convex hulls into convex hulls, and 
preserve the uniformity of statistical
distributions. From these facts it follows that
$\bar h(n)$ is the same for all affine
images of a given figure; and, since any triangle can be mapped
into any other by some affine transform, $\bar h(n)$ is the same
for all triangles.\par

\sect{4.8. Other distributions.}

R\'enyi and Sulanke were aslo able to compute the asymptotic
expansion of $\bar h(n)$ for a few other distributions. If the points are
uniformly distributed over a fixed convex polygon $K$ with vertices
$a
1, a
2, \ldotss, a
r$, then
we have
$$\bar h(n)= {{2 r}\over3}(\ln n + \gamma) +
  {2\over 3}\bigglp\sum
{1\leq i\leq r}\ln{f
i\over{F}}\biggrp +
   o(1)\eqno(19)$$
where $f
i$ is the area of the triangle $a
{i-1}a
ia
{i+1}$, and $F$
is the area of $K$.\par

This result may seem paradoxical: suppose $K$ is a triangle,
and suppose an infinitesimally small piece $K\pr$ is removed
from one of its corners. According to formula (19), the average
number of vertices in the convex hull jumps from $2\ln n + O(1)$
to ${8\over 3}\ln n + O(1)$. The paradox is resolved by observing
that the $O(1)$ terms in these two expressions obscure the
difference between the coefficients of $\ln n$ for small $n$.
When $n$ is large enough to show this difference, the probability
of finding a point in $K\pr$ has become significant --- i.e.,
$K\pr$ is no longer infinitesimally small.\par

If the points are uniformly distributed on a circle, the average value of $h$ is
$$\bar h(n)=2\Gamma(5/3)\left({{2\pi^2}\over3}\right)^{1/3}
n^{1/3}\,(1+o(1)).\eqno(20)$$
In fact, we have $\bar h(n)=O(n^{1/3})$ whenever the points are
uniformly distributed over an {\it arbitrary} convex figure with smooth
boundary; the shape of the curve changes only the proportionality factor.\par

They also show that
$$\bar h(n)=2\sqrt{2\pi\ln n}\,(1+o(n))\eqno(21)$$
if the points come from a two-dimensional normal distribution.
Looking at the table in section 4.6, we conclude that, in all the
cases discussed so far,
the average time required by algorithm 4.3 (Preparata-Houy) is just
$O(n)$.\par

\sect{4.9. The Floyd-Eddy algorithm.}

Since we are discussing average-case analysis, it is appropriate to
mention here a simple algorithm for the convex hull of $n$ points in
the plane, due to R. Floyd and W. Eddy (1977), that also runs in $O(n)$
average time. This algorithm assumes that, in adition to the set
$P$, two reference points $q,r\not\in P$ are given such that all
points of $P$ are contained in some parallelogram $K$ whose base
is the segment $qr$.
The parallelogram should be on the right side of the oriented line
from $q$ to $r$.\fig4
The algorithm will return the vertex sequence $\langle q, p
1, p
2,
\ldotss, p
h, r \rangle$ of $\hull(P\un \leftset q, r \rightset)$.\par 

\algorithm{4.7}{Convex hull by recursive line sweeps.} {
\step 1. [Find extremal point.] {Find the point $p\in P$ whose distance from
line $qr$ is maximum. If $P$ is empty, or $p$ is on the segment $qr$,
then return $\langle q, r\rangle$}
\step 2. [Split the set.] {Let $Q\subset P$ be the set of those points
which are strictly to the right of the oriented line from $q$ to $p$; likewise,
let $R$ be that of the points to the right of line $pr$.}
\step 3. [Apply recursion.] {Apply the algorithm recursively to the set
$Q$, with reference points $q$ and $p$, and to $R$, with reference
points $p$ and $r$. Let $\langle q, q
1, q
2, \ldotss, q
i, p\rangle$
and $\langle p, r
1, r
2, \ldotss, r
j, r\rangle$ be the resulting hulls.}
\step 4. [Combine answers.] {Return the sequence $\langle q, q
1, q
2,
\ldotss, q
i, p, r
1, r
2, \ldotss, r
j, r\rangle$ and stop.}}

The correctness of this algorithm is easily established with the help
of theorem 3.24. The fact that $p$ is at maximum distance from the line $qr$
is equivalent to saying that by sweeping the plane with a line parallel to $qr$
the point $p$ is encounterd last; therefore,  $p$ is a vertex of
$\hull(P\un \leftset q, r \rightset)$.
From the hypothesis and from the choice of $p$, we know also
that $Q$ and $R$ are contained in the regions $I$ and $II$ of the
figure below, and this implies the correctness of the
result computed in step 4.\par

To compute $\hull(P)$ for an arbitrary set $P$ of points in the plane, we
can find the points $q,r\in P$ with maximum and minimum $x$-coordinate,
and split $P-\leftset q, r \rightset$ in two parts: $P
1$ above
the line $qr$, and $P
2$ below it. By applying the algorithm above
to $(P
1, q, r)$ and to $(P
2, r, q)$ and concatenating the results
we get $\hull(P)$, as desired. Note that $P
1$ will be contained
in some parallelogram $K
1$ with base $qr$ and vertical sides,
and a similar thing will hold for $P
2$.\par

To analyze the average runtime of algorithm 4.7, we assume the points
of $P$ are uniformly distributed in some convex figure $F\subset K$
that contains $q$ and $r$. After
point $p$ has been determined, we know the remaining points are
uniformly distributed in the region $F\pr=F\inte K\pr$, where $K\pr$ is the portion of $K$ below the line through $p$ parallel to $qr$.\fig4
Because of the
convexity of $F$, we know the triangle $qpr$ is inside $F\pr$,
and from elementary geometry we know that its area is half that
of $K\pr$. On the average, one-half or more of the remaining points
of $P$ will be in this triangle, and therefore will be included neither in
$Q$ nor in $R$. From the table in section 4.6, we see that
$\alpha+\beta\leq{1\over 2}<1$ and $S(n)+M(n)=O(n)$
imply $H(n)=O(n)$.\par

To complete the arguments above we must make sure the initial
assumptions of algorithm 4.7 are verified also by the recursive
calls it generates. It suffices to note that the triangular regions
I and II
(and therefore $Q$ and $R$) are contained in the parallelograms
$K
I, K
{II}$ with bases $qp$ and $pr$, respectively;
their non-basal sides
can be taken to be parallel to the segment $qr$. The
points in $Q$ and $R$ will be uniformly distributed on the
convex regions $F
I=F\pr\inte K
I$ (containing $q$ and $p$) and
$F
{II}=F\pr\inte K
{II}$ (containing $p$ and $r$).

\sect {4.9. Lower bounds for convex hull determination.}

In this section we will discuss
briefly some lower bounds for the complexity of finding
the convex hull of $n$ points in the plane.
There are two slightly different ways to formulate
this problem, depending on whether the vertices of the hull are to
be returned in counterclockwise order, or whether we are allowed
to list them in any order.\par

The first problem is easily shown to be at least as hard (in the worst case)
as the problem of sorting  $n$ distinct numbers,
and therefore requires $\Theta(n\log n)$
time to solve. The correspondence can be established by
scaling the numbers to be sorted $x
1, x
2, \ldotss, x
n$
so that they fall in the range
$0\leq x
i \leq\pi$, and defining the point set $P=\leftset (\cos x
i, \sin x
i)
\relv 1\leq i\leq n\rightset\un\leftset (0,-1)\rightset$
(these computations take only linear time).
Then we will have $\hull(P)=P$, and
the vertices of $\hull(P)$ in counterclockwise order, starting from
$(-1, 0)$, correspond to the numbers $x
i$ in ascending order.

The ``unsorted hull'' problem is not affected by this
argument, however. The only obvious lower bound is linear (since
we must look at each of the given points at least once); yet no
algorithm is known that achieves this bound, and in fact
A. Yao has proved the following result (1981):\par

\theorem{4.5}{Any algorithm that finds the convex hull of
$n$ points in the plane using only quadratic tests on the
coordinates of those points requires $\Omega(n\log n)$ such tests
in the worst case.}

By ``quadratic test'' we mean a test of the form
$f(x
1, y
1, x
2, y
2, \ldotss,
x
m, y
m)\geq0$ (or $\null>0$, $\null=0$, etc.), where
$F$ is a second-degree polynomial
and the $x
i,y
i$ are the coordinates of input points.
Note that the logical tests performed by the algorithms we discussed
so far (like the cross-product test, or the
function $\prg{SameSide($p$, $q$, $r$, $s$)}$) can be rewritten using a
bounded number of such quadratic tests. This holds even
if we allow the tests to be applied to intermediate variables,
as long as these are linear functions of the inputs. As a matter of fact, all
convex hull algorithms that can be found in the literature perform
only quadratic tests on the input points, so theorem 4.5 is
extremely important.\par

For a given value of $n$, a convex hull algorithm can be
``unfolded'' so as to become a binary decision tree, where each
internal node $t$ is associated with a fixed quadratic test
$f
t(x
1, y
1, x
2, y
2, \ldotss, x
n, y
n)geq0$ and
each leaf $s$ with a subset $N
s$ of $\leftset 1, 2, \ldotss, n\rightset$.
Each input $P=\leftset p
1, p
2, \ldotss, p
n\rightset$, defines a
path in this tree, where the edge taken after each internal node $t$ is
determined by whether $P$ satisfies or fails the associated test $f
t$.
The leaf $s$ where this path ends is such that $\hull(P)=
leftset p
i \relv i\in N
s\rightset$.\par

The central idea of Yao's proof is the following.
Let n=2m, and let $R^*$ be a regular polygon with $m$ vertices
$\leftset r
1^*, r
2^*, \ldotss, r
n^*\rightset$.\par

For each permutation $\sigma$ of $1, 2, \ldotss, m$,
define the family $\Pscr
\sigma$ as being the collection of all
$2m$-point sets $P=\leftset r
1, r
2, \ldotss, r
m, q
1, q
2,
\ldotss, q
m\rightset$, where $\leftset r
1, r
2, \ldotss, r
m\rightset$ is a
``slightly perturbed'' copy of $R^*$, and each
$q
i$ is a point on the segment $r
{\sigma(i)}r
{\sigma(i)+1}$
\foot1{Here, as usual, we assume the $r
i$ to be cyclically
indexed, i.e. $r
i$ actually means $r
{(i-1)\modop m + 1}$.} and
somewhere near its middle point:\fig5\par

For each member $P=\leftset r
1, r
2, \ldotss, r
m, q
1, q
2,
\ldotss, q
m\rightset$ of $\Pscr
\sigma$, we have
$\hull(P)=\leftset r
1, r
2,\ldotss, r
m\rightset$, but the points
$q
1, q
2, \ldotss, q
m$ are on the ``boundary'' of decision:
an infinitesimal change in their coordinates would be
enough to make them vertices of the hull. When the algorithm
is applied to  such $P$,
it must check each $q
{\sigma(i)}$ against the adjacent
vertices $r
i$ and $r
{i+1}$ for collinearity. In doing so, the
algorithm will essentially determine for each $q
{\sigma(i)}$ the
corresponding side $r
ir
{i+1}$, i.e. it will determine the
permutation $\sigma$. To distinguish between the $m!$ possible
permutations, the algorithm needs al least $\lg (m!) = \Omega(n\log n)$
tests.\par

Of course, this argument is little more than hand-waving, but unfortunately
the details are too complex to give here in full. For them, the reader is
referred to the original paper  in JACM 28,4 (Oct. 1981) 780--787.\par 

\vfill\eject\end
(635)\f5 13277i1I