How to adapt "System of Circles" method to 3D for finding a sphere given 4 points?

Question

I want to analyze (computational complexity & running time) of different approaches to determining a sphere in 3D given 4 points on its surface. To start I have been searching for different methods of determining a circle in 2D given 3 points on its circumference, and I found a nice webpage, link below, that describes 7 distinct methods for accomplishing this in 2D.

http://www.qc.edu.hk/math/Advanced%20Level/circle%20given%203%20points.htm

Now I am trying to study how, if possible, each method described for circles in 2D can be modified to be done in 3D for spheres, and I am having difficulty. Specifically I am interested in method #5 from the link above, the "System of Circles" method. Summarizing from the above linked page:

$$ \text{Find the equation of the circle passing through the points: } \\ P=(-6,5), Q=(-3,-4), R=(2,1) \\ $$ $$ \text{Equation of line PQ:} \\ \frac{y-y_2}{x-x_2}=\frac{y_1-y_2}{x_1-x_2} \\ \frac{y+4}{x+3}=\frac{5+4}{-6+3} \\ 3x + y + 13 = 0 \\ $$ $$ \text{Circle with line PQ as diameter:} \\ (x +6)(x+3) + (y –5)(y + 4) = 0 \\ x^2+y^2+9x-y-2=0 \\ $$ $$ \text{System of circles (that contain PQ as a cord):} \\ x^2+y^2+9x-y-2+k(3x + y + 13)=0 \\ $$ Then substituting in the x & y values from the remaining point, R, you can solve for the k value that generates the specific circle also passing through R. $$ 2^2+1^2+9(2)-(1)-2+k[3(2) + (1) + 13]=0 \\ k=-1 \\ \text{Thus the desired circle passing through P, Q, & R is:} \\ x^2+y^2+9x-y-2-(3x + y + 13)=0 \\ x^2+y^2+6x-2y-15=0 \\ $$

To summarize this approach in 2D it first determines a line between 2 of the 3 points, then determines a circle (different from the one desired) where that line is a diameter, then creates an expression (system?) that generates all circles that contain that line as a cord, then solves this expression for the desired circle by substituting in the 3rd point.

What would be the proper way of converting this approach to finding a sphere given 4 points on its surface in 3D?

When first trying to adapt this to 3D I immediately stumbled when realizing there isn't a "two point form" for the equation of a line with 3D points. But then, I realized I probably don't even want to create a line, and then a circle around that line anyway. Wouldn't the proper thing be to find the equation of a circle through 3 of the 4 3D points, and then create an expression for all spheres intersected by that circle? And then solve for the specific sphere that also contains the 4th point? If this is the correct approach how does one first determine a circle containing 3 3D points? Everything I read about circles, such as the web page linked above, is only in terms of 2D points.

Answer 1

Let $(x_{k},y_{k},z_{k})$ be your four sets of coordinates. Form the following matrix (each set of patentheses is one row), then take its determinant via minors of the first row and set the result to zero. That is your equation.

$(x^{2}+y^{2}+z^{2} x y z 1)$

$(x_{1}^{2}+y_{1}^{2}+z_{1}^{2} x_{1} y_{1} z_{1} 1)$

$(x_{2}^{2}+y_{2}^{2}+z_{2}^{2} x_{2} y_{2} z_{2} 1)$

$(x_{3}^{2}+y_{3}^{2}+z_{3}^{2} x_{3} y_{3} z_{3} 1)$

$(x_{4}^{2}+y_{4}^{2}+z_{4}^{2} x_{4} y_{4} z_{4} 1)$

Why it works: For the equation of a sphere you need a linear combination of $x^{2}+y^{2}+z^{2}, x, y, z,$ and $1$ equal to zero. The determinant just described does that at all four specified points by putting $(x,y,z) = (x_{k},y_{k},z_{k})$ into the first row.

Answer 2

You'll want to completely understand the 2D problem: Circumcircle of Triangle. The solution is based on symmetry. Sketch an arbitrary triangle, and the circumcircle. Each triangle edge is a chord of the circle. Plot the perpendicular bisector of each chord...these three lines intersect at the center of the circumcircle. The radius of the circle is simply the distance from the center to any triangle vertex.

3D Problem: Circumsphere of arbitrary tetrahedron

The trick is to find the same symmetry, except in 3D. Sketch your tetrahedron. The faces consist of 4 3D triangles. Each triangle has a 3D circumcircle...sketch these for at least two triangular faces. Now sketch the perpendicular axis of each 3D circle. These 3D lines intersect at the center of the circumsphere (assuming infinite-precision numerical representations).

In reality, with finite precision numerics as you get on a computer, the two axes come VERY CLOSE to intersecting at the circumsphere's center. (Numerical imprecision guarantees that the lines DO NOT intersect). The solution is to process the two skew lines with an algorithm that finds their midpoint of closest approach line segment.

You can sketch a 3D solution, but to solve this problem numerically is too much for pencil and paper...it requires computation to handle the number crunching.

The key representations and algorithms needed are:

circumcircle of triangle (2D)

arbitrary coordinate rotation in 3D (using 3x3 rotator matrix)

circumcircle of triangle (3D)

representation for 3D circle

representation of 3D extended line

closest approach line segment of two skew lines

Speed: The above algorithm is O(k), meaning it's a direct algorithm (no searching or iteration), and the inputs are small & fixed in number, so efficiency needn't be improved upon.

Edge-case handling: Four given points can always be solved for their circumsphere given that their tetrahedron is well-formed. However, a robust algorithmic solution should screen out tetrahedrons that are approaching degeneracy. These are extremely squat shapes (barely thicker than a 3D triangle), and sliver-like shapes that only have extent along one direction. For slivers, degeneracy checking may be done on the individual triangular faces. For the squat tetrahedron, degeneracy must be checked in 3D.