Aligning Points to Lines: Provable Approximations
  We suggest a new optimization technique for minimizing the sum $\sum_{i=1}^n
f_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-time is polynomial in $n$ for the fundamental problem of
\emph{Points-to-Lines alignment}: Given $n$ points $p_1,\cdots,p_n$ and $n$
lines $\ell_1,\cdots,\ell_n$ on the plane and $z>0$, compute the matching
$\pi:[n]\to[n]$ and alignment (rotation matrix $R$ and a 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, the running time of our algorithms is $O(n^3)$, 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 provable 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.
