## 2 Related Work  
In this section, we provide reviews on: (i) methods for naive and robust rotation search, (ii) methods for naive and robust point cloud registration, and (iii) heuristics for robust outlier rejection. **Rotation search:** The rotation search (also called \"Wahba\") problem was first proposed by [PERSON] in [1], in order to estimate the attitude of satellites from the observation of vectors. It can be solved in closed form based on either a rotation matrix [30; 31; 32; 33] or the quaternion-based parametrization [34; 35], although these methods usually fail in the existence of outliers. It is known to all that in the process of building vector correspondences using the feature descriptors [16; 17] based on 2D or 3D keypoints, it is likely to obtain false results and mismatches, that is the so-called _outliers_. Thus, robust solvers are required. The BnB framework is effective at finding the optimal rotation from the outlier-corrupted corresponding vectors, and the typical examples include the first globally optimal method searching over the rotation space [36], the L2-distance-based approach [37], and the speeded up angular-distance-based solution [38]. In addition to BnB, guaranteed outlier removal [21] is another way to estimate the rotation robustly and is generally faster than the BnB solvers. Some other robust rotation search solvers are also the subroutines for point cloud registration problems (e.g., [20; 22; 25]), which will be later discussed in the review on point cloud registration. **Point cloud registration:** To solve the point cloud registration problem, the Iterative Closest Point (ICP) [39] is a common local-minimum approach, but it is too dependent on the initial guess of the transformation, thus prone to fail without a good initialization. Therefore, an initialization-free way to address the registration problem--to build correspondences between point clouds from 3D keypoints [40] using feature descriptors (e.g., FPFH [17], ISS [41], and FCGF [42]), has grown increasingly popular. Many correspondence-based methods have been proposed to address the registration problem in the presence of noise. For example, it can be solved using closed-form solutions [32; 34] by decoupling the estimation of rotation, scale, and translation. BnB has also been applied to solve the registration problem [43] in a globally optimal way. More recently, the Lagrangian dual relaxation was developed to produce a globally optimal generalized registration solver [14] for handling point-to-point, point-to-line, and point-to-plane registration with optimality guarantees. However, the 3D feature descriptors generally have lower accuracy and robustness compared with 2D ones [15; 16], which could result in relatively higher or even extreme outlier ratios in some real-world scenes, as was discussed in [20]. The above-mentioned solutions are fairly sensitive and can be fragile once there exist outliers among the correspondences, which consequently demands the following robust registration methods. The minimal closed-form solutions [32; 34] can be fit into the RANSAC family frameworks [18; 28; 29] to deal with outliers, though they may be slow when the outlier ratio is high. Another idea to be robust is that: if as many outliers can be guaranteed to be removed or eliminated as possible, then what remains should be mostly inliers. GORE [20] is such a preprocessing outlier removal approach that guarantees that the correspondences removed must not be inliers. In terms of the nonminimal robust solvers, FGR [22] is the first method using Graduated Nonconvexity (GNC) to reject outliers, which estimates the rigid transformation matrix with a Gauss-Newton method. Though not globally optimal, FGR is efficient for known-scale registration. Currently, TEASER/TEASER++ [24; 25] are the more robust nonminimal certifiably globally optimal solvers that can tolerate 99% outliers in known-scale situations. Another recent solution [44] utilizes RANSAC for scale and translation estimation and also adopts GNC to solve the rotation.