\input CS445Hdr
% This is CS445E1.tex of January 18, 1982 10:35 PM
\def\title{Lectures 1--2}
\def\header{E1. Errata et Addenda --- Chapters 1--2}

\chap{\header.}

\sect{E1.1. A faster algorithm for the minimum spanning sphere.}

Ken Clarkson remarked that at each iteration of algorithm 2.3 (mss in $k$ dimensions), only one of the $k+1$ points that determine the current spanning sphere is changed. Therefore, the system of equations that is to be solved at each step is identical to the previous one except for a single equation. If the inverse of the coefficient matrix for the previous step is known, the new inverse (and the solution vector) can be computed in time $O(k↑2)$, instead of $O(k↑3)$ or $O(k↑{2.5-})$. This optimization gives an algorithm that runs in $O(k↑2n↑2)$.

\sect{E1.2. A glitch in algorithm 2.3.}

In the comments following algorithm 2.3, it is claimed that when the current sphere is not minimum, then either at most one of the coefficients $\alphaǐ$ is negative, or their sum is greater than 1. This is equivalent to say that the center of the sphere passing through $k+1$ points is either inside the $k$-simplex determined by those points, or is separated from it by exactly one of its supporting hyperplanes. It was pointed out to the author of these notes (who wishes to remain anonymous) that this is not true for $k\geq3$; for example, one can inscribe a tetrahedron in a sphere in such a way that the center is separated from the tetrahedron by the planes of {\it two} faces (see figure).\fig5 This does not seem to affect the correctness of the algorithm, though.

\vfill\eject\end