Purdue University

West Lafayette, IN 47907

USA

We are given four spheres S_{k}, k=1..4, with centers s_{k} and radii
r_{k}, and seek to determine all lines L that are tangent to those four
spheres. The problem arises, for example, in spatial geometric constraint
solving, either as stated, or else when we seek to construct a line L that is to
have a specific distance r_{k} from known points s_{k},
where k=1...4. We prove that there can be up to 12 such tangents in general,
using the method of [1] and refer to a recent result [2] that shows that this
bound is exact.

Assume that L has the coordinates (x,y,z;u,v,w), where (x,y,z) is the point
of L closest to the origin and (u,v,w) is the line direction vector. Note that the same line
in the opposite direction has the coordinates (x,y,z;-u,-v,-w). Now
choose a coordinate system in which the first sphere has its center s_{1}=(0,0,0)
at the origin, the second sphere has s_{2}=(a,0,0) on the x-axis, the center s_{3}=(b,c,0)
is in the xy-plane, and the center s_{4}=(d,e,f) is in general position.
We obtain six equations that express the constraints on the line L, namely:

x^{2}+y^{2}+z^{2}-R_{0}=0 |
(1) |

(x-a)^{2}+y^{2}+z^{2}-(au)^{2}-R_{1}=0 |
(2) |

(x-b)^{2}+(y-c)^{2}+z^{2}-(bu+cv)^{2}-R_{2}=0 |
(3) |

(x-d)^{2}+(y-e)^{2}+(z-f)^{2}-(du+ev+fw)^{2}-R_{3}=0 |
(4) |

xu+yv+zw=0 |
(5) |

u^{2}+v^{2}+w^{2}=1 |
(6) |

where R_{k} = r_{k}^{2}.

The algebraic degree of that system is 64. Furthermore, note that if (x,y,z;u,v,w) is a solution of the system, then so is (x,y,z;-u,-v,-w).

We can use equations (2), (3) and (4) to solve for x, y, and z. We obtain the following expressions:

x= | (a^{2}-a^{2}u^{2}-R_{1}+R_{0})/(2a) |

y= | (ab^{2}-a^{2}b+a^{2}bu^{2}+bR_{1}-bR_{0}+ac^{2}-ab^{2}u^{2}-2abcuv-ac^{2}v^{2}-aR_{2}+aR_{0})/(2ac) |

z= | -(K_{0 }+ K_{1}uv + 2acefvw + 2acdfuw + K_{2}u^{2}
+ K_{3}v^{2} + acf^{2}w^{2}) /
(2fac) |

where | |

^{ }K_{0}= |
ace^{2}+dcR_{0}-dcR_{1}+dca^{2}
-acd^{2}+aeR_{0}-aeR_{2}+aec^{2}-ebR_{0}+ebR_{0}-eba^{2}
+aeb^{2}-acR_{0}+acR_{3}-acf^{2}_{ } |

^{ }K_{1}= |
2acde - 2abce_{ } |

^{ }K_{2}= |
acd^{2} - dca^{2} - aeb^{2} + bea^{2}_{ } |

^{ }K_{3}= |
ace^{2}_{ }- aec^{2} |

Substituting them into equations (1), (5) and (6) results in three equations in the unknowns u, v, and w, where the algebraic degrees are 4, 3, and 2, respectively. Thus, the new system has a total degree of 24.

Note that in the expressions for x, y, and z the variables u, v, and w appear only quadratically. Therefore, the new system also has the property that for each solution (x,y,z;u,v,w) there is a solution (x,y,z;-u,-v,-w). Therefore, at most 12 geometrically distinct tangents can exist.

In [2], the authors consider the case of equal radii and analyze both the general position and the degenerate positions. They give an example of four unit spheres that are centered at the vertices of a tetrahedron and have exactly 12 real tangents. Therefore, the bound of 12 tangents is exact.

- C. M. Hoffmann and Bo Yuan, On Spatial Constraint Solving Approaches, presented at the Workshop for Automated Deductions in Geometry, ETH Zürich, September 2000.
- I. G. Macdonald, J. Pach and T. Theobald,
Common Tangents to Four Unit
Balls in R
^{3}, to appear in J. of Discr. and Comp. Geometry.