# minimum distance between two arbitrary circles in space

as per the title, i am working out the problem with maxima, but i am surprised by how complicated this rapidly turns out to unfold for such a "simple" question.

monstrous equations, maybe someone has a bright idea? thanks.

-
For circles that are far apart, draw a line segment between their centers and project this segment onto each circle. This should work whenever the line segment is larger than the sum of the two radii. For circles that are closer, it does get more complicated. Gerhard "Ask Me About System Design" Paseman, 2012.04.12 –  Gerhard Paseman Apr 12 '12 at 19:08
The only other idea I have is that the line joining the two closest points (assuming no intersections) should be proved to be perpendicular to tangent lines to each circle in their respective planes. Gerhard "Ask Me About System Design" Paseman, 2012.04.12 –  Gerhard Paseman Apr 12 '12 at 19:12
I have a similar two circle problem related to packing. I am close to giving up and asking here if someone will help me with the analytic geometry involved. Gerhard "Ask Me About System Design" Paseman, 2012.04.12 –  Gerhard Paseman Apr 12 '12 at 19:19

See "Finding the distance between two circles in three-dimensional space," by C.A. Neff, in the IBM Journal of Research and Development, Volume 34, Number 5, Page 770 (1990). IBM link. From the Abstract:

We show, by combining a theorem about solvable permutation groups and some explicit calculations with a computer algebra system, that, in general, the distance between two circles is an algebraic function of the parameters defining them, but that this function is not solvable in terms of radicals.

Another source is David Eberly's "Distance Between Two Circles in 3D," PDF link. His unpublished note gives explicit instructions for the computation, without analyzing its algebraic complexity too carefully. He does say that a critical equation

can be reduced to a polynomial of degree 8 whose roots ... are the candidates to provide the global minimum...

-
Unfortunately, I cannot access the IBM journal article easily. –  Joseph O'Rourke Apr 12 '12 at 21:32
To me it seems like a rather vain hope to think its purely solvable by radicals. But presumably there's a fairly simple piecewise solvable-by-radicals solution ? –  Ryan Budney Apr 12 '12 at 21:37
The critical points are the roots of a polynomial whose coefficients are analytic in the parameters of the circles. The only thing that could be "piecewise" is which root gives the minimum. The polynomial can be solvable by radicals for some particular values of the parameters (e.g. those for which the answer is obvious by symmetry), but not for "generic" values. –  Robert Israel Apr 15 '12 at 5:04
@Robert: Thanks for the explanation! –  Joseph O'Rourke Apr 15 '12 at 13:35

Use rational parametrizations of the circles (e.g. $\cos(\theta) = \frac{1-s^2}{1+s^2}$, $\sin(\theta) = \frac{2s}{1+s^2}$) with parameters $s$ and $t$ (hoping that the minimum is not when the parameter is $\infty$), let $F(s,t)$ be the square of the distance between the points on the circles for parameter values $s$ and $t$, and take the resultant of $\partial F/\partial s$ and $\partial F/\partial t$ with respect to one of $s$ and $t$. You should get a polynomial (I think of degree $20$) whose real roots will correspond to critical points.

-
Degree 20? Wow. Are you willing to tackle a packing problem which might result only in a polynomial of degree 8? Gerhard "Ask Me About System Design" Paseman, 2012.04.12 –  Gerhard Paseman Apr 12 '12 at 19:36
If you are, it is a modification of this MathOverflow posting mathoverflow.net/questions/24184 . If one has to pack two circles the problem is easily resolved. My version is more challenging because I take a chord of distance 1/2 radius from the center of the large circle, chop off the smaller piece, and try to pack the two circles into the larger piece. It is easily achievable for most pairs of circles, but I can't prove it for all appropriate pairs. Gerhard "Willing To Retask Comment Fields" Paseman, 2012.04.12 –  Gerhard Paseman Apr 12 '12 at 19:48
Actually it's not quite so bad as degree $20$, because $(1+s^2)^4$ or $(1+t^2)^4$ is a factor. –  Robert Israel Apr 12 '12 at 23:35

I didn't manage to solve the problem (edit: in the meantime an answer was posted which says a precise formula using radicals cannot be found), but I can post a proof that the line joining the points where the minimal/maximal distance is achieved is perpendicular to the tangent line at the circles in those contact points. (inspired by the comment of Gerhard Paseman)

To do this, choose $\vec{a}$ and $\vec{d}$ the position vectors of the centers and $\vec{b},\vec{c}$, respectively $\vec{e},\vec{f}$ be two pairs of orthogonal unit vectors which span the planes of the first and respectively the second circle. Denote by $r,s$ the radii of the two circles. Consider the circles parametrized as (in fact, the argument works for any parametrization) $$p(\theta)=\vec{a}+r\cos\theta\ \vec{b}+r\sin\theta\ \vec{c}, \ \theta \in [0,2\pi]$$ $$q(\tau)=\vec{d}+s\cos\tau\ \vec{e}+s\sin\tau\ \vec{f}, \tau \in [0,2\pi]$$ and denote $F(\theta,\tau)=|p(\theta)-q(\tau)|^2$. Then the pair of points which realize the minimal/maximal distance must satisfy $$\frac{\partial F}{\partial \theta}=\frac{\partial F}{\partial \tau}=0.$$

We have $$\frac{\partial F}{\partial \theta}=2\sum_{i=1}^3 [p_i(\theta)-q_i(\tau)]p_i'(\theta)=2 (p(\theta)-q(\tau))\cdot p'(\theta)$$ $$\frac{\partial F}{\partial \tau}=-2\sum_{i=1}^3 [ p_i(\theta)-q_i(\tau) ] q_i'(\tau)=-2 (p(\theta)-q(\tau))\cdot q'(\tau)$$ where "$\cdot$" is the usual dot product. Therefore when $\theta,\tau$ correspond to the minimum/maximum value, the partial derivatives vanish and $p'(\theta)\perp (p(\theta)-q(\tau))$ and $q(\tau)'\perp (p(\theta)-q(\tau))$ where $p'(\theta),q'(\tau)$ are the tangent vectors in the contact points and $p(\theta)-q(\tau)$ is the vector connecting the points where minimal/maximal distance is achieved.

-