1
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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:

  1. fixing the line parameters $\mathbf{q},\mathbf{v}$ and optimizing for closest points for each other line $t_i$, and
  2. 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).

$\endgroup$
5
  • $\begingroup$ Why is it obvious that the solution must pass through the origin? How does non-convexity imply this? $\endgroup$
    – yig
    Commented Feb 7, 2018 at 4:14
  • $\begingroup$ In 2D, any line not parallel to any of the given set will intersect all of them (distance zero). The horizontal and vertical lines will be local maxima. In the L1 norm, any horizontal or vertical line passing through the unit square will have equal cost. In the L2 norm horizontal and vertical lines passing through the origin will have lower cost. 45-degree diagonal lines will be somewhat worse local maxima than horizontal or vertical lines, because the diagonal distance between the unit square corners is greater than the horizontal or vertical ones. $\endgroup$
    – yig
    Commented Feb 7, 2018 at 4:31
  • $\begingroup$ Ah, you're right about 2D. I had originally imagined 3D and erroneously simplified it. Suppose you have all the lines on edges of a cube, instead. If the minimizer doesn't go through the origin, then the L2 energy is non-convex by symmetry. Similarly by symmetry, the L2 energy is either non-convex or the minimizer must pass through each face center. But a line cannot pass through all 6 face centres, implying non-convexity. $\endgroup$ Commented Feb 7, 2018 at 5:04
  • $\begingroup$ I don’t see why the line must pass through the origin, but I do see that face centers are local minima in the L2 norm and a line can’t pass through all six of them. Therefore, it would be non-convex. For the L1 norm, all points on all faces are equal good, so non-convexity isn’t clear to me. $\endgroup$
    – yig
    Commented Feb 7, 2018 at 6:45
  • $\begingroup$ If the local minima can be enumerated, the global minima may be findable. $\endgroup$
    – yig
    Commented Feb 7, 2018 at 6:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .