Aligning Points to Lines: Provable Approximations

We suggest a new optimization technique for minimizing the sum
$\sum _{i=1}^n g_i(x)$
of
$n$
non-convex real functions that satisfy a property that we call piecewise log-Lipschitz. This is by forging links between techniques in computational geometry, combinatorics and convex optimization. As an example application, we provide the first constant-factor approximation algorithms whose running-times are polynomial in
$n$
for the fundamental problem of
Points-to-Lines alignment
: Given
$n$
points
$p_1,\ldots,p_n$
and
$n$
lines
$\ell _1,\ldots,\ell _n$
on the plane and
$z>0$
, compute the matching
$\pi :[n]\to [n]$
and alignment (rotation matrix
$R$
and translation vector
$t$
) that minimize the sum of euclidean distances
$\sum _{i=1}^n \mathrm{dist}(Rp_i-t,\ell _{\pi (i)})^z$
between each point to its corresponding line. This problem is non-trivial even if
$z=1$
and the matching
$\pi$
is given. If
$\pi$
is given, our algorithms run in
$O(n^3)$
time, and even near-linear in
$n$
using core-sets that support: streaming, dynamic, and distributed parallel computations in poly-logarithmic update time. Generalizations for handling e.g., outliers or pseudo-distances such as
$M$
-estimators for the problem are also provided. Experimental results and open source code show that our algorithms improve existing heuristics also in practice. A companion demonstration video in the context of Augmented Reality shows how such algorithms may be used in real-time systems.