Smallest sphere intersecting lines in R^3 I have N lines in R^3 (that are very likely skew). I'm looking for an efficient method of computing the radius (and position) of the smallest sphere that intersects every line.
I suspect that there's a solution related to the 'smallest sphere enclosing points' problem, but I failed to find it.
(The purpose is to be able to do bundle adjustment without needing to make the inferred point positions visible to the optimizer).
 A: The distance from a point to a line is a convex function, and the maximum of convex functions in convex, so locating a point that minimizes the maximum of its distances to the lines is a convex problem, therefore it should be relatively easy to solve using modern software for convex optimization.
A: Here is a starting point. For each line $L$ in $\newcommand{\bR}{\mathbb{R}}$ $\bR^3$ we denote by $C_r(L)$ the cylinder of axis $L$ and radius $R$. Given  $N$ lines you need to find  the smallest $r$ such that the convex sets $C_r(L_1),\dotsc, C_r(L_N)$ have nonempty overlap.
According to Helly's theorem,  a collection of convex subsets  in $\bR^k$ has nonempty overlap if and only if, any subcollection of $k+1$ subsets in that  collection has a nonempty overlap. Thus, in your case, you need to make sure  that  any four cylinders in your collection  have nonempty overlap.
This reduces the problem to $N=4$ which looks less scary, yet still challenging.
If we are given $4$-lines  $L_1,\dotsc, L_4$ passing through   distinct point $p_1,\dotsc, p_4$  and spanned by the unit vector $\newcommand{\bu}{\boldsymbol{u}}$ $\bu_1,\dotsc,\bu_4$, then the distance  from a point $x$ to the line $L_k$ is achived along a segment $[x, y]$ where,
$$y\in L_k,\;\; [x,y]\perp L_k. $$
This means
$$y= p_k+t\bu_k,\;\;  (x-p_k -t\bu_k, \cdot \bu_k)=0, $$
so that
$$ t=(x-p_k, \bu_k),\;\; y= p_k +(x-p_k, \bu_k)\bu_k, $$
$${\rm dist}(x, L_k)^2=\bigl| x-p_k -(x-p_k,\bu_k)\bu_k\;\bigr|^2=|x-p_k|^2-(x-p_k,\bu_k)^2. $$
At this point some ugly, but  machine approachable algebra is needed.
