{'fraction_non_alphanumeric': 0.04425363276089828, 'fraction_numerical': 0.0066050198150594455, 'mean_word_length': 4.8949416342412455, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Provably Approximated Point Cloud Registration

The goal of the alignment problem is to align a (given) point cloud P = {p1, ⋯,pn} to another (observed) point cloud Q = {q1, ⋯,qn}. That is, to compute a rotation matrix R ∈ ℝ3×3 and a translation vector t ∈ ℝ3 that minimize the sum of paired distances between every transformed point Rpi − t, to its corresponding point qi, over every i ∈ {1, ⋯,n}. A harder version is the registration problem, where the correspondence is unknown, and the minimum is also over all possible correspondence functions from P to Q. Algorithms such as the Iterative Closest Point (ICP) and its variants were suggested for these problems, but none yield a provable non-trivial approximation for the global optimum.We prove that there always exists a "witness" set of 3 pairs in P × Q that, via novel alignment algorithm, defines a constant factor approximation (in the worst case) to this global optimum. We then provide algorithms that recover this witness set and yield the first provable constant factor approximation for the: (i) alignment problem in O(n) expected time, and (ii) registration problem in polynomial time. Such small witness sets exist for many variants including points in d-dimensional space, outlier-resistant cost functions, and different correspondence types.Extensive experimental results on real and synthetic datasets show that, in practice, our approximation constants are close to 1 and our error is up to x10 times smaller than state-of-the-art algorithms.