\input CS445Hdr
% This is CS445N2.tex of January 18, 1982 11:45 PM

\def\title{Lectures 1--2}
\def\header{The minimum spanning circle}

\chap {2. \header.}
\sect {2.1. The problem.}
\def\msc{\mathop{\hbox{\rm msc}}}
\def\mss{\mathop{\hbox{\rm mss}}}
\def\lfv{\leftv}
\def\rtv{\rightv}

The first problem we will study is the
computation of the {\it minimum spanning circle} ($\msc$) of a
given finite set $P=\{p1̌, p2̌, \ldotss, pň\}$ of points in the plane,
which is defined to be the circle
of smallest radius that contains all points of $P$.\par

Before we develop an algorithm for computing the $\msc$,
we should make sure that it is a well-defined
entity, by showing that it exists and is unique.
We see immediately that if $P$ is empty,
any circle of zero radius will contain all points,
so the $\msc$ will not be unique. Also, if all points of $P$ coincide,
the $\msc$ is trivial. Therefore, in what follows we will assume
that $P$ has at least two distinct points.\par

Let $d$ be the {\it diameter} of the set $P$, i.e.
$d=\max \leftset \dist(p, q)\relv p,q\in P \rightset$.
It is clear that a circle centered at any point of $P$ and with radius $d$
will contain all points of $P$. This shows that the set of spanning
circles is nonempty, and implies that the radius $r$
of the $\msc$ is no greater than $d$.\par

This bound is not tight, and it is easy to improve. Let
$p$ and $q$ be two points of $P$ at distance $d$, and consider the
circles $A$ and $B$ centered at $p$ and $q$ with radius $d$.
\fig3
It is obvious that any circle containing both $p$ and $q$ must have
radius at least $d/2$.
On the other hand, the set $P$ is contained
in the intersection of the two circles $A$ and $B$, and
therefore is contained in a smaller circle $C$
centered at $m$, the midpoint
of segment $pq$. The radius of this circle is $d{{\sqrt 3}/2}$, the
height of an equilateral triangle whose side is $d$.
We conclude therefore that
$$ {d \over 2} \leq r \leq {{d\sqrt 3} \over 2}.$$
This upper bound is not yet optimal, as we will see.\par

It is well known that a bounded, nonempty set does not always have a minimum
element, as for example $\leftset x\in \real \relv 0<x\leq 1\rightset$.
To prove the existence and uniqueness of a $\msc$, we need the following
results:\par

\lemma{2.1}{For any circle $A$ spanning $P$, and any
two points $a$, $b$ on its boundary,
there is a spanning circle $B$ passing through $a$ and $b$
that is no greater than $A$
and either (1) has segment $ab$
for diameter, or (2) passes through a point $p\in P$, distinct
from $a$ and $b$, in such a way that the arc $apb$ is greater than $\pi$.}
\proof{ Note that $a$ and $b$ may be coincident and need not
belong to $P$.
The esential idea is that we can ``shrink’’ $A$ a little bit,
keeping it anchored at $a$ and $b$ and
pushing its center towards the segment $ab$, until the center becomes
the midpoint of $ab$ of we hit another point of $P$.
The following paragraphs make this idea
more precise.
\fig5
Let $o$ be the center of $A$, and $m$ be the midpoint of segment $ab$.
Let $B0̌$ be the smallest circle that passes through $a$ and $b$,
i.e. the circle with $ab$ as diameter.\par

\hp Let $q1̌, q2̌, \ldotss, qǩ$
be the points of $P$ contained in $A-B0̌$. For $1\leq i\leq m$,
define $Bǐ$ to be the circle with center in the segment $om$
and passing through $a, b$ and $qǐ$. It is easy to show that
$Bǐ$ contains $B0̌\inter A$ and is not larger than $A$.
It is also easy to see that for any $i$ and $j$ (including $0$)
we have $Bǐ-B0̌\subset Bǰ-B0̌$ iff the radius of
$Bǐ$ is less than or equal to that of $Bǰ$.\par

\hp If we let $B$ be the largest of $B0̌, B1̌, \ldotss, Bǩ$,
we can see that $B$ contains $A\inter B0̌$ and $q1̌, q2̌,
\ldotss, qǩ$. Since the remaining points of $P$ are in
$A\inter B0̌$, $B$ contains all points of $P$.
If $B$ is $Bǐ$ with $i>0$, then $qǐ$ will be on its boundary,
and the arc $aqǐb$ will be greater than $\pi$ (case 2); otherwise
we will have case 1.}

This lemma enables us to prove the following:\par

\lemma{2.2}{If $A$ is a spanning circle of $P$, then
there exists a spanning circle $B$ not greater than $A$
that (1) passes through two distinct
points $p, q$ of $P$ and has segment $pq$ for diameter, or (2) passes
through three distinct points of $P$.}
\proof{Let $a=b$ be any point in the boundary of $A$, and
apply lemma 2.1, obtaining a circle $B\pr$. $B\pr$ cannot have
$ab$ for diameter, since the diameter of $P$ is positive;
therefore it must pass through a
point $p$ of $P$. Apply lemma 2.1 again, this time with $a=b=p$, and
let $B\prr$ be the resulting circle.\par

\hp By the same argument, $B\prr$
passes through two distinct points $p, q\in P$. Another
application of lemma 2.1, with $a=p$ and $b=q$ yields a spanning circle $B$
which either has segment $pq$ for diameter (satisfying case 1)
or contains a third point $s\in P$ (case 2).}

With these lemmas, plus the fact that
there is only one circle passing through three given distinct points,
we are ready to prove the existence of the $\msc$:\par

\theorem{2.3}{A finite
set $P$ of points in the plane with at least two distinct
elements has a unique $\msc$ that
is (1) a circle passing through two points
$p,q\in P$ and having $pq$ for diameter, or (2) a circle passing
through three distinct points of $P$.}
\proof{We know that $P$ has at least one spanning circle. By lemma 2.2
we know that for every spanning circle there is another that is no greater than it and satisfies (1) or (2) above. The set of such
circles is finite (it has at most ${n \choose 2} + {n \choose 3}$
elements) and therefore has an element $B$ with
minimum radius. Any other spanning circle of $P$ (in this set or not)
will have a radius greater than or equal to that of $B$.\par

\hp Now suppose that there were two distinct $\msc$s for $P$, say $B\pr$
and $B\prr$. Since they
intersect (both contain $P$) and have
distinct centers $o, o\pr$,
they have positive (and equal) radii:
\fig3
But then $P$ is contained in their
intersection, which in turn
is contained in the circle $C$ (see figure) which is
strictly smaller than both.}

This theorem gives us a finite algorithm for finding the $\msc$:\par

\algorithm{2.1}{Minimum spanning circle of $n$ points in the plane.}{
\step 1. [Initialize.] {Let $B$ be the whole plane.}
\step 2. [Ennumerate two-point circles.] {
For each pair $p,q$ of points in $P$,
construct the circle $C$ with $pq$ for diameter, and perform step 5.}
\step 3. [Ennumerate three-point circles.] {For each triplet $p,q,s$,
find $C$, the (only) circle that passes through them, and perform step 5.}
\step 4. [Done.] {Terminate the algorithm and
return $B$ as result.}
\step 5. [Select minimum circle.] {If $C$ is smaller than $B$ and
contains all points of $P$, set $B\gets C$.}}

This algorithm takes time $O(n↑4)$: there are $O(n↑3)$ circles to consider,
and it takes $O(n)$ to check each circle against the remaining points.

To improve on this algorithm, we need a stronger version of theorem 2.3,
that is developed in the next section.\par

\sect{2.2. An improved algorithm.}

\lemma {2.4}{The $\msc$ of three distinct points that constitute
a non-obtuse triangle is the circle passing through them.}
\proof{Let $p,q$ and $s$ be the three points, and $A$ be its
$\msc$. Suppose $A$ doesn’t pass trough $s$; then, by theorem 2.3,
it must have segment $pq$ as diameter. Since $s$ is strictly inside
$A$, and the arc $pq$ opposite to $s$ is a half circle, the angle
$psq$ at $s$ must be greater than $\pi / 2$ -- a contradiction. It follows
that $A$ passes through $s$. In the same way, we can show that
it passes through $p$ and $q$.}

Let’s call an arc of a circle {\it point-free} if it
passes through no point of $P$ (except maybe at its endpoints).
The following holds:

\lemma {2.5}{If a spanning circle is minimum then its boundary
contains no point-free arc larger than $\pi$.}
\proof{Suppose a spanning circle $A$
contains a point-free arc $a\alpha b$ greater than $\pi$; we will show that
$A$ is not minimum. By lemma 2.1
there exists another circle $B$ through $a$ and $b$ not greater than
$A$ that either has segment $ab$ for diameter or has an arc $aqb$ greater
than $\pi$ with $q\in P$.
\fig3
In the first case the radius of $B$ is
strictly smaller than $A$, and we are done. In the second case, assume
that the two circles have the same radii; since they are distinct
(one contains $q$ and the other doesn’t), they must be arranged as in the
figure above, and then the smaller circle $C$ is also a spanning
circle.}

\lemma {2.6}{If a circle $A$ has no point-free arc greater than $\pi$,
then it passes through two diametrically opposite points of $P$, or
through three points of $P$ that determine an acute
triangle.}
\proof {If P passes through two diametrically opposite points of
$P$, we are done. Otherwise,
let $p\in P$ be a point on the circle boundary, and let $p\pr$ (which is
not in $P$)
be its diametrically opposite point.
\fig3
Let $st$ be
the largest point-free arc of $A$ containing $p\pr$ (so $s,t\in P$).
The arc $st$ is less than $\pi$, by hypothesis; $ps$ and $tp$ are
so by construction. It follows that the triangle $pst$ is acute.}

The next result is an immediate consequence of the three preceding lemmas:\par

\theorem{2.7}{A spanning circle $A$ is minimum iff it passes through two
diametrically opposite points, or though three points that define an acute
triangle.}

With this result we can improve the upper bound for $r$,
the radius of the $\msc$:\par

\theorem{2.8 {\rm(H. W. E. Jung)}}{$${d \over 2} \leq r \leq {{d
\sqrt 3} \over 3}.$$}
\proof{The lower bound $r\geq {d/2}$ is trivial; let’s show the upper one.
If the $\msc$ $A$ passes through diametrically opposite points,
obviously $r=d/2\leq d\sqrt3/3$. Otherwise, by theorem 2.7, it
passes through three points of $p,q,s\in P$ that define an acute triangle.
Let $o$ be the center of the circle $A$.
\fig4
Without loss of generality, we can assume that $pq$ is the
largest side of the triangle $pqs$, so
the arc $p\alpha q$ of $A$ opposite to $s$ is between ${2\over3}\pi$
(120\deg) and $\pi$.
Since the triangle $poq$ is isosceles, angle $qpo$ will be
at most ${1\over2}(\pi-{2\over3}\pi) = \pi/6$ (30\deg), and therefore we have
$$r = {{\seg{pq}/2}\over {\cos {\angle qpo}}}
\leq {{\seg{pq}/2}\over{\cos {\pi\over 6}}}$$
Since $\seg{pq}\leq d$ and $\cos {\pi\over6} = {\sqrt 3/2}$, we get
$$ r\leq {{d/2}\over{{\sqrt3}/2}}={{d\sqrt3}\over3}$$}

What is more important, theorem 2.7 gives us a better algorithm
for computing the $\msc$:

\algorithm{2.2}{Improved algorithm for $\msc$ of $n$ points in the plane.}{
\step 1. [Initialize.] {Find a pair of points $a,b\in P$ such that all
points of $P$ are on the same half-plane $A$ determined by
the line passing through $a$ and $b$.}
\step 2. [At this point $A$ is a spanning circle passing through
$a,b$.] {Let $B$ be the circle with diameter $ab$, and do
$c\gets a$.}
\step 3. [Expand B.] {For each point $p\in P-\{a,b\}$ which is
outside $B$, find the circle $Bp̌$ passing
through $a, b$ and $p$; set $B\gets Bp̌$, $c\gets p$.}
\step 4. [Now $B$ is a spanning circle not greater than $A$ passing
through $a,b$.] {If the triangle $abc$ has an angle greater than $\pi/2$, remove
the corresponding vertex from $P$, set $a$ and $b$ to
the remaining two vertices, set $A\gets B$, and go back to step 2.
Otherwise, we are done and $B$ is the $\msc$.}}
\proof{If we regard the half-plane $A$ computed in step 1
as being a degenerate
circle of infinite radius, we can see that steps 2 and 3 carry out
the construction used in the proof of lemma 2.2. Following that proof,
we conclude that, at the beginning
of step 4, $B$ is a spanning circle of $P$.\par

\hp If we terminate in step 4, the answer will be correct by theorem 2.7.
Otherwise, we have to show that the deleted vertex is not relevant
for the determination of the $\msc$, and then the correctness will
follow by induction.
\fig3
The removed vertex must be either $a$ or $b$, for the arc $ab$ opposite
to $c$ is $\pi$ initially and never increases; let’s assume it is $a$.
Suppose the $\msc$ $B\pr$
of $P-\{a\}$ were not the same as that of $P$; it would
have to be smaller (by the uniqueness property), and, to contain $b$
and $c$, it would have to contain $a$. But then $B\pr$ would
span $P$, a contradiction.}

The variable $A$ is superfluous, and was included in the algorithm
only to clarify its relationship to lemma 2.2. $A$ is always
a spanning circle of $P$.\par

One way to perform step 1 is to find a point $a\in P$ with minimum
ordinate, and then select, among the points $b\in P$ with $xb̌>xǎ$,
the one for which the slope of segment $ab$ (i.e., $(yb̌-yǎ)/(xb̌-xǎ)$)
is minimum. Clearly, this and step 3 can both
be done in $O(n)$ time. Steps 2 and 3 are
executed $O(n)$ times in the worst case,
so the whole algorithm takes $O(n↑2)$.\par

This is not yet the fastest known algorithm; as we will
see later in the course, it is possible to compute $\msc(P)$
in $O(n\log n)$ steps.\par

Since this is the first topic of the course, the proofs in this
section have been intentionally carried to minute details; due to lack of
time and space, we may be somewhat less rigorous in the next
chapters. Note, however, that the proofs above are not yet perfect:
geometric intuition is used at certain points,
and some degenerate cases have not been explicitly
covered. Consider for example what should be done
when $a, b$ and $p$ are collinear in step 3 of the above algorithm.\par

\sect{2.3. Generalization to higher dimensions.}

Suppose $P$ is a set of points in $k$-dimensional Euclidean space $\Sscr$,
and we are interested in finding its {\it minimum spanning sphere},
($\mss$), the smallest $k$-dimensional sphere containing all points.\par

The theorems and algorithms above generalize nicely, if the concept
of ``triangle’’ is replaced by that of a
{\it $k$-dimensional simplex}, a convex
region of $\Sscr$ with $k+1$ vertices. A $k$-dimensional simplex
is bounded by
$k+1$ {\it faces}, each defined by a $(k-1)$-dimensional subspace of $\Sscr$
(an {\it hyperplane}) that passes through $k$ vertices of the simplex.\par

The analogous of algorithm 2.2 is the following:

\algorithm {2.3}{Minimum spanning sphere of $n$ points in $k$-space.}{
\step 1. [Find a face of the convex hull.] {
Find an hyperplane determined by a $k$-point subset $F$ of $P$,
such that one of the corresponding half-spaces, $A$, contains all points of P.}
\step 2. [Now $A$ is a spanning $k$-sphere passing through $F$.] {
Let $B$ be the smallest $k$-sphere
passing through the points of $F$. Let $c$ be any point of $F$.}
\step 3. [Expand $B$.] {For each point $p$ in $P-F$ not contained in $B$,
compute the $k$-sphere $Bp̌$ passing through all the points $F\union \{p\}$;
set $B\gets Bp̌$ and $c\gets p$.}
\step 4. [Now $B$ is a spanning $k$-sphere of $P$ that passes through
$F\union \{c\}$.] {If the center of $B$ is inside or on
the boundary of the $k$-dimensional simplex
defined by $F\pr = F\union \{c\}$, the algorithm
terminates and $B$ is the $\mss$.
Otherwise, find a face $F\pr-\{a\}$ of the
simplex $F\pr$ whose supporting hyperplane separates the center from
the opposite vertex $a$; delete $a$ from $P$, set $F\gets F\pr-\{a\}$,
$A\gets B$, and return to step 2.}}

To determine the center of the $k$-sphere passing through a given
set of $k+1$ points, proceed as follows. Denote by $x{̌ij}$ the $j$-th
coordinate of the $i$-th point; let $c1̌, c2̌, \ldotss, cǩ$ be
the coordinates of the center, and $r$ be the radius. Then
$$\sum{̌j=1}↑k{(x{̌ij}-cǰ)↑2} = r↑2\eqno{(1)}$$
has to hold for each $i$. These non-linear equations can be
rewritten as follows:
$$\sum{̌j=1}↑k{x{̌ij}↑2}-2\sum{̌j=1}↑k{x{̌ij}cǰ}+\sum{̌j=1}↑k{cǰ↑2}=r↑2$$
or also
$$\sum{̌j=1}↑k{x{̌ij}cǰ}+{1\over2}(r↑2-\sum{̌j=1}↑k{cǰ↑2})
={1\over2}\sum{̌j=1}↑k{x{̌ij}↑2}.$$

Notice that the second term on the left-hand side does not depend
on $i$. If we let $h$ stand for that term, we get
$$\sum{̌j=1}↑k{x{̌ij}cǰ}+h={1\over2}\sum{̌j=1}↑k{x{̌ij}↑2}
\eqno{(2)},$$
for $i=1,2,\ldotss,k+1$, which is a linear system of equations
on the $k+1$ unknowns $c1̌,c2̌,\ldotss,cǩ$ and $h$. As it is
known, such system can be solved in $O(k↑3)$ by standard techniques,
or in $O(k↑{2.5-})$ using methods related to the ``fast’’
matrix multiplication algorithms.

The same technique is used in step 2 to find the smallest sphere
through $k$ (instead of $k-1$) points. The first $k$ equations of (2)
determine a one-dimensional subspace containing $c$ that
is orthogonal to the hyperplane containing the $k$ points,
so $c$ can be found by projecting any of them onto this subspace.

To perform the test in step 4 and to find the vertex to be deleted,
we can use the following method: define $vǐ$ to be the vector from
point $x{̌k+1}$ to $xǐ$, and express the center $c$ as
$x{̌k+1}$ plus a linear combination $\alpha1̌v1̌+\alpha2̌v2̌+\cdots+
\alphaǩvǩ$ of the $vǐ$.
If the center is inside the simplex, all coefficients in the
linear combination should be nonnegative and their sum should be
at most 1. Otherwise, either the sum is greater than 1 (and $x{̌k+1}$ is
to be deleted) or exactly one of the $\alphaǐ$ will be negative
(and then $xǐ$ is to be deleted). The computation of the $\alphaǐ$
reduces to the solution of a $k\times k$ system of linear equations.\par

The total time required by algorithm 2.3 is therefore $O(k↑{2.5-}n↑2)$.
It should be noted that the $O(n \log n)$ method alluded
at the end of the previous section doesn’t seem to generalize to
higher dimensions, so algorithm 2.3 is the best known for $k\geq3$.\par

This is a situation that seems to be
quite common in computational
geometry: the fastest known algorithm for a two-dimensional problem
becomes very slow, or cannot be used at all, when the problem is extended
to higher dimensions, and is then outperformed by other methods that are much
slower in the planar case.

\vfill\eject\end