Aligning Points to Lines: Provable Approximations
Ibrahim A. Jubran, Dan Feldman · IEEE Transactions on Knowledge and Data Engineering · 2020
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 ofPoints-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.