Today I was reading this article by Ericson. The article is on the derivation involved in writing a function to calculate the minimum bounding sphere of a set of three or four points. The topic itself isn’t very interesting (to me) when compared to the algebra itself. Ericson skips the algebra I had trouble with, so my article here will serve the purpose to record the algebra he skipped (in case other readers had trouble, or I ever want to reference the math again). The article I am writing here directly follows Ericson’s article, so I will assume readers have read and understood Ericson’s article.

Say we have a set of three points S = {A, B, C}, which can be thought of as a triangle. The problem of calculating the minimum bounding sphere of S involves checking to see if the *circumcenter* of S lies within or outside the triangle S. Lets name the circumcenter P. One immediate implementation involves computing P, followed by the computation of the barycentric coordinates of P with respect to S. These coordinates can be used check if P lay within S.

However computing P of S followed by the barycentric coordinates of P with respect to S involves a lot of redundant computations. Furthermore, if P does not lay within S then P itself does not need to be computed at all, since only the barycentric coordinates were needed.

It would be nice to compute barycentric coordinates of P with respect to S directly, and only if necessary construct P.

P in relation to S can be defined as:

\begin{equation}

\label{eq1}

P = A + s*(B – A) + t*(C – A)

\end{equation}

Where \(s\) and \(t\) are barycentric coordinates of S such that \(s – t – (1.0 – s – t) = 0\) if P is within S. Since P is equidistant from A, B and C, we can express P in relation to S with the following:

\begin{equation}

\label{eq2}

dot(P – B, P – B) = dot(P – A, P – A)

\end{equation}

\begin{equation}

\label{eq3}

dot(P – C, P – C) = dot(P – A, P – A)

\end{equation}

The interesting part involves plugging \eqref{eq1} into \eqref{eq2} and \eqref{eq3} followed by a collection of terms. Since I myself am a noob when it comes to algebra I had to go look up algebraic properties of the dot product to make sure I did not screw anything up. In particular these few rules are useful:

\begin{equation}

\label{eq4}

dot(u, v + w) = dot(u, v) + dot(u, w) \\

dot(s * u, v) = s*dot(u, v) \\

-dot(u – v, u – w) = dot(v – u, u – w)

\end{equation}

Lets go over substituting \eqref{eq1} into \eqref{eq2} directly, however lets only consider the first part of \eqref{eq2} \(Dot(P – B, P – B)\) to keep it simple:

\begin{equation}

\label{eq5}

dot(A + s*(B – A) + t*(C – A) – B, A + s*(B – A) + t*(C – A) – B)

\end{equation}

Since things immediately get really long some substitutions help to prevent errors:

\begin{equation}

\label{eq6}

u = A – B\\

v = s*(B – A) + t*(C – A)\\

w = u + v \\

\end{equation}

\begin{equation}

\label{eq7}

Dot(w, u + v)

\end{equation}

\begin{equation}

\label{eq8}

Dot(w, u) + Dot(w, v)

\end{equation}

\begin{equation}

\label{eq9}

Dot(u + v, u) + Dot(u + v, v)

\end{equation}

\begin{equation}

\label{eq10}

Dot(u, u) + Dot(v, u) + Dot(u, v) + Dot(v, v)

\end{equation}

If I were to expand \eqref{eq10} on this webpage it would not fit. Instead we will make use of a few more substitutions and then arrive in the final form:

\begin{equation}

\label{eq11}

x = s*(B – A) \\

y = t*(C – A) \\

x + y = v

\end{equation}

\begin{equation}

\label{eq12}

Dot(A – B, A – B) + 2*Dot(A – B, x + y) + Dot(x + y, x + y)

\end{equation}

By following the same process we can finish the substitution and notice that:

\begin{equation}

\label{eq13}

Dot(P – A, P – A) = Dot(x + y, x + y)

\end{equation}

The final form of the substitution would be:

\begin{equation}

\label{eq14}

Dot(A – B, A – B) + \\ 2*Dot(A – B, x + y) + \\ Dot(x + y, x + y) = Dot(x + y, x + y)

\end{equation}

\begin{equation}

\label{eq15}

Dot(A – B, A – B) + 2*Dot(A – B, x + y) = 0

\end{equation}

\begin{equation}

\label{eq16}

Dot(A – B, A – B) + \\ 2*Dot(A – B, s*(B – A)) + \\ 2*Dot(A – B, t*(C – A)) = 0

\end{equation}

\begin{equation}

\label{eq17}

s*Dot(B – A, B – A) + t*Dot(B – A, C – A) = \\ (1/2)*Dot(B – A, B – A)

\end{equation}

This final equation \eqref{eq17} matches exactly what Ericson came up with on his own blog. Through a similar process \eqref{eq1} can be substituted into \eqref{eq3}, which would result in:

\begin{equation}

\label{eq18}

s*Dot(C – A, B – A) + t*dot(C – A, C – A) = \\ (1/2)*dot(C – A, C – A)

\end{equation}