## 4 Compatible Structures in the Point Cloud Registration Problem
### COS in Rotation Search  
The basic structure in rotation search for constrained random sampling is the COS that consists of a pair of correspondences as introduced below. **Definition 2** (2-COS and length-based invariants). : _Assume we have 2 vector correspondences such that \((\mathbf{u}_{i},\mathbf{v}_{i}),i=1,2\), defined as a 2-COS. We first normalize them all to unit length such that:_  
\[\mathbf{u}_{1}^{*}=\frac{\mathbf{u}_{1}}{||\mathbf{u}_{1}||},\ \mathbf{v}_{1}^{*}=\frac{ \mathbf{v}_{1}}{||\mathbf{v}_{1}||},\ \mathbf{u}_{2}^{*}=\frac{\mathbf{u}_{2}}{||\mathbf{u}_{2}||},\ \mathbf{v}_{2}^{*}= \frac{\mathbf{v}_{2}}{||\mathbf{v}_{2}||}. \tag{11}\]  
_Then, we derive the following pairwise length-based invariants as:_  
\[I_{12}^{l}=||\,||\mathbf{u}_{1}^{*}-\mathbf{u}_{2}^{*}||-||\mathbf{v}_{1}^{* }-\mathbf{v}_{2}^{*}||\,||=\epsilon_{12}^{l}, \tag{12}\]  
_where \(I_{12}^{l}\) represents the length-based invariant w.r.t. this pair of correspondences and \(\epsilon_{12}^{l}\) denotes the noise measurement (perturbative) on this invariant._  
Intuitively, invariant \(I_{12}^{l}\) represents the length difference between the third sides of the two triangles formed by the corresponding vector pairs over the two frames. Without noise perturbance, \(I_{12}^{l}\) should be strictly equal to 0 as long as the correspondences pf this pair are both inliers. However, with noise, we can still impose a constraint on \(I_{12}^{l}\) to examine whether this correspondence pair might contain outliers. **Proposition 1** (Constraints on \(l_{12}^{l}\)). : _For the pairwise invariant \(l_{ij}^{l}\) in the 2-COS defined above, we can derive that:_  
\[l_{12}^{l}\leq L, \tag{13}\]  
_where \(L\) denotes the bound w.r.t. noise satisfying the inequality such that \(L^{*}+||\epsilon||\cdot\left(\left\|\frac{1}{\mathbf{v}_{1}}\right\|+\left\| \frac{1}{\mathbf{v}_{2}}\right\|\right)\)\(\leq L\), in which \(L^{*}=\left\|\frac{\mathbf{u}_{1}}{||\mathbf{v}_{1}||}-\frac{\mathbf{u}_{2}}{|| \mathbf{v}_{2}||}-\frac{\mathbf{u}_{1}}{||\mathbf{u}_{1}||}+\frac{\mathbf{u}_ {2}}{||\mathbf{u}_{2}||}\right\|\)._  
Proof. : Based on the triangular inequality and the fact that norm \(\|\cdot\|\) is invariant of \(R\), we can always have:  
\[ \begin{split}|\,||\mathbf{u}_{1}^{*}-\mathbf{u}_{2}^{*}||-|| \mathbf{v}_{1}^{*}-\mathbf{v}_{2}^{*}||\,|\\ =\left|\|\mathbf{R}\|\cdot\left\|\frac{\mathbf{u}_{1}+\mathbf{R} ^{\top}\boldsymbol{\epsilon}_{1}}{||\mathbf{v}_{1}||}-\frac{\mathbf{u}_{2}+ \mathbf{R}^{\top}\boldsymbol{\epsilon}_{2}}{||\mathbf{v}_{2}||}\right\|- \left\|\frac{\mathbf{u}_{1}}{||\mathbf{u}_{1}||}-\frac{\mathbf{u}_{2}}{|| \mathbf{u}_{2}||}\right\|,\\ \leq L^{*}+\|\mathbf{R}^{\top}\|\cdot\left\|\frac{\boldsymbol{ \epsilon}_{1}}{||\mathbf{v}_{1}||}-\frac{\boldsymbol{\epsilon}_{2}}{||\mathbf{ v}_{2}||}\right\|\\ \leq L^{*}+\left\|\frac{\boldsymbol{\epsilon}_{1}}{||\mathbf{v}_ {1}||}\right\|+\left\|\frac{\boldsymbol{\epsilon}_{2}}{||\mathbf{v}_{2}||} \right\|=L,\end{split}  \tag{14}\]  
where the length-based inequality (13) can be proven. If we have obtained an eligible 2-COS, we can compute the rotation w.r.t. this pair of correspondences using [PERSON]'s triad-based matrix transformation [34] such that:  
\[ \begin{split}\mathbf{O}_{1}&=\big{[}\begin{array}[] {cc}\mathbf{u}_{1}&(\mathbf{u}_{1}\times\mathbf{v}_{1})&\mathbf{u}_{1} \times(\mathbf{u}_{1}\times\mathbf{v}_{1})\end{array}\big{]},\\ \mathbf{O}_{2}&=\big{[}\begin{array}{cc}\mathbf{u}_{2}&(\mathbf{u}_{2}\times \mathbf{v}_{2})&\mathbf{u}_{2}\times(\mathbf{u}_{2}\times\mathbf{v}_{2})\end{array} \big{]},\\ &\mathbf{R}_{12}=\mathbf{O}_{2}\mathbf{O}_{1}^{\top}=\mathbf{R}_{ gt}Exp(\boldsymbol{\rho}_{12}),\end{split}  \tag{15}\]  
where \"\(Exp\)\" maps the size-3 noise measurement (vector) \(\boldsymbol{\rho}_{12}\) to the rotation (for explicit derivations, please refer to Section 7.1.3 in [50]), and \(\mathbf{R}_{gt}\) denotes the ground truth rotation. Then, we further try to build a 3-COS by adding a new correspondence with this 2-COS, based on which new constraints can be imposed.