.png){kind=icon}
返回
Aligning Points to Lines: Provable Approximations
.png){kind=icon}
OA
AI
DOI：10.1109/TKDE.2020.2980836.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
We suggest a new optimization technique for minimizing the sum Sigma(n)(i=1) 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),...,p(n) and n lines l(1),...,l(n) on the plane and z > 0, compute the matching pi : [n] -> [n] and alignment (rotation matrix R and translation vector t) that minimize the sum of euclidean distances Sigma(n)(i=1) dist(Rp(i) - t, l(pi(i)))z between each point to its corresponding line. This problem is non-trivial even if z = 1 and the matching p is given. If p 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 .
Keyword:
Approximation algorithms
non-convex optimization
visual tracking
points-to-lines alignment
coresets
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
10.4
论文数:
6.8K
被引数:
3.2W
机构
引用论文
.png){kind=icon}
分享收藏
查看更多内容