# Minimum Bounding Sphere

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:

\label{eq1}
P = A + s*(B – A) + t*(C – A)

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:

\label{eq2}
dot(P – B, P – B) = dot(P – A, P – A)

\label{eq3}
dot(P – C, P – C) = dot(P – A, P – A)

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:

\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)

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:

\label{eq5}
dot(A + s*(B – A) + t*(C – A) – B, A + s*(B – A) + t*(C – A) – B)

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

\label{eq6}
u = A – B\\
v = s*(B – A) + t*(C – A)\\
w = u + v \\

\label{eq7}
Dot(w, u + v)

\label{eq8}
Dot(w, u) + Dot(w, v)

\label{eq9}
Dot(u + v, u) + Dot(u + v, v)

\label{eq10}
Dot(u, u) + Dot(v, u) + Dot(u, v) + Dot(v, v)

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:

\label{eq11}
x = s*(B – A) \\
y = t*(C – A) \\
x + y = v

\label{eq12}
Dot(A – B, A – B) + 2*Dot(A – B, x + y) + Dot(x + y, x + y)

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

\label{eq13}
Dot(P – A, P – A) = Dot(x + y, x + y)

The final form of the substitution would be:

\label{eq14}
Dot(A – B, A – B) + \\ 2*Dot(A – B, x + y) + \\ Dot(x + y, x + y) = Dot(x + y, x + y)

\label{eq15}
Dot(A – B, A – B) + 2*Dot(A – B, x + y) = 0

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

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

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:

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

Share