Closest line to a set of lines in 3D In $\mathbb{R}^3$, given a set of lines $S$, find a line $L$ that minimizes
$$
\sum_{s_i \in S} D( L, s_i )
$$
where $D( \cdot , \cdot )$ is the Euclidean distance between two lines (defined as the distance between their closest points).
I would also be happy to have an answer minimizing other metrics, like the sum of squared distances, the median distance, or the maximum distance.
 A: Depending on the set of lines, this is a non-convex energy minimization problem.
There still might be a practical algorithm for finding a solution. One way to re-write this problem is as a minimization of closest distances:
$$
\min_{\mathbf{q},\mathbf{v}} \sum_{i=1}^n \left( \min_{t_i} 
\left\|
(\mathbf{q}+t_i\mathbf{v}-\mathbf{p}_i)-
((\mathbf{q}+t_i\mathbf{v}-\mathbf{p}_i)\cdot\mathbf{u}_i)\mathbf{u}_i
\right\|^2
 \right)
$$
where $\mathbf{q}$ and $\mathbf{v}$ are a point and the direction vector of your line $L$ and $\mathbf{p}_i$ and $\mathbf{u}_i$ are a point and the direction vector on the $i$th line $s_i$ in your set of lines $S$.
This is very similar in form to the typical form minimized by the iterative closest point (ICP) algorithm.
In this case, a minimal algorithm would proceed by repeatedly:


*

*fixing the line parameters $\mathbf{q},\mathbf{v}$ and optimizing for closest points for each other line $t_i$, and 

*fixing $t_i$ and optimizing for $\mathbf{q},\mathbf{v}$.


The optimal $\mathbf{q},\mathbf{v}$ are found with a linear system solve involving all lines in $S$, while each optimal $t_i$ can be found in parallel.
This optimization probably benefits from all the usual tricks for ICP 
like stochastic gradient descent, Gauss Newton (a.k.a., point-to-plane in ICP), and perhaps Alternating Direction Method of Multipliers (ADMM).
