Aligning Points to Lines: Provable Approximations.

We suggest a new optimization technique for minimizing the sum $\sum _{i=1}^n g_i(x)$ ∑ i = 1 n g i (x) of $n$ 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$ n for the fundamental problem of Points-to-Lines alignment: Given $n$ n points $p_1,\ldots,p_n$ p 1 ,... , p n and $n$ n lines $\ell _1,\ldots,\ell _n$ ℓ 1 ,... , ℓ n on the plane and $z>0$ z > 0 , compute the matching $\pi :[n]\to [n]$ π : [ n ] → [ n ] and alignment (rotation matrix $R$ R and translation vector $t$ t ) that minimize the sum of euclidean distances $\sum _{i=1}^n \mathrm{dist}(Rp_i-t,\ell _{\pi (i)})^z$ ∑ i = 1 n dist (R p i - t , ℓ π (i)) z between each point to its corresponding line. This problem is non-trivial even if $z=1$ z = 1 and the matching $\pi$ π is given. If $\pi$ π is given, our algorithms run in $O(n^3)$ O (n 3) time, and even near-linear in $n$ 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$ 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. [ABSTRACT FROM AUTHOR]