## 4 Compatible Structures in the Point Cloud Registration Problem
### COS in Point Cloud Registration  
The basic structure in point cloud registration lies in the COS with 3 correspondences. **Definition 3** (3-COS and pairwise scale-based invariants). : _Assume that we obtain 3 non-collinear point correspondences \((\mathbf{\mathrm{P}}_{i},\mathbf{\mathrm{Q}}_{i}),i=1,2,3\), defined as one 3-COS. We can derive the following pairwise scale-based invariants:_  
\[I_{ij}^{s}=\frac{||\mathbf{\mathrm{Q}}_{i}-\mathbf{\mathrm{Q}}_{j}||}{||\mathbf{\mathrm{P }}_{i}-\mathbf{\mathrm{P}}_{j}||}=s_{gt}+\varepsilon_{ij}^{s}, \tag{22}\]  
_where \((i,j)\in\{(1,2),(1,3),(2,3)\}\), \(I_{ij}^{s}\) represents the scale-based invariant w.r.t. the \(i\)th and the \(j\)th correspondences, \(s_{gt}\) denotes the ground truth scale, and \(\varepsilon_{ij}^{s}\) denotes the noise measurement on the scale._  
Figure 2: Overview of the inlier searching process of ICOS. We start by finding eligible \(a\)-COS across the two point sets, then seek new correspondences that can establish \(b\)-COS with the existing \(a\)-COS and eventually stop sampling when we collect a sufficient number of eligible \(b\)-COS (\(b=a+1\)). Then, we can endow each pair of scale-based invariants \(I_{ij}^{s}\) with constraints given as follows:  
**Proposition 3** (Constraints on \(I_{ij}^{s}\)). : _For any two invariants \(I_{ij}^{s}\) in the 3-COS, we can derive that:_  
\[|I_{ij}^{s}-I_{jk}^{s}|\leq A\Bigg{(}\frac{1}{||\mathbf{P}_{i}-\mathbf{P}_{j}|| }+\frac{1}{||\mathbf{P}_{j}-\mathbf{P}_{k}||}\Bigg{)} \tag{23}\]  
_where \((i,j,k)\in\{(1,2,3),(2,3,1),(3,1,2)\}\) (here, \(I_{ij}^{s}\) and \(I_{ji}^{s}\) denote the same invariant) and \(A\) is the noise bound, satisfying that \(2||\boldsymbol{\epsilon}||\leq A\). In addition, when the scale is known (\(s_{gt}=1\)), we can further have that:_  
\[|I_{ij}^{s}-1|\leq A\Bigg{(}\frac{1}{||\mathbf{P}_{i}-\mathbf{P}_{j}||}\Bigg{)}. \tag{24}\]  
Proof. : It is easy to have that:  
\[s_{gt}\mathbf{R}_{gt}\mathbf{P}_{ij}+\epsilon_{ij}=\mathbf{Q}_{ij},\Rightarrow \ ||s_{gt}\mathbf{R}_{gt}\mathbf{P}_{ij}||=||\mathbf{Q}_{ij}-\epsilon_{ij}||, \tag{25}\]  
where \(\mathbf{P}_{ij}=\mathbf{P}_{i}-\mathbf{P}_{j}\), \(\mathbf{Q}_{ij}=\mathbf{Q}_{i}-\mathbf{Q}_{j}\), and \(\epsilon_{ij}=\epsilon_{i}-\epsilon_{j}\). Using the triangular inequality, we can derive that:  
\[||\mathbf{Q}_{ij}||-||\boldsymbol{\epsilon}_{ij}||\leq||s_{gt}\mathbf{R}_{gt} \mathbf{P}_{ij}||=s_{gt}||\mathbf{P}_{ij}||\leq||\mathbf{Q}_{ij}||+|| \boldsymbol{\epsilon}_{ij}^{s}||, \tag{26}\]  
so that:  
\[s_{gt}-\frac{||\boldsymbol{\epsilon}_{ij}||}{||\mathbf{P}_{ij}||}\leq\frac{|| \mathbf{Q}_{ij}||}{||\mathbf{P}_{ij}||}\leq s_{gt}+\frac{||\boldsymbol{ \epsilon}_{ij}||}{||\mathbf{P}_{ij}||}. \tag{27}\]  
Thus, Inequalities (23) and (24) can be derived as long as we have: \(||\boldsymbol{\epsilon}_{ij}||\leq||\boldsymbol{\epsilon}_{i}||+||\boldsymbol {\epsilon}_{j}||=2||\boldsymbol{\epsilon}||\leq A\). Subsequently, we calculate the raw scale \(s_{123}\) as:  
\[s_{123}=\frac{1}{\sum_{1}^{3}\omega_{ij}}\cdot\sum_{1}^{3}\omega_{ij}\frac{ \|\mathbf{Q}_{ij}\|}{\|\mathbf{P}_{ij}\|}, \tag{28}\]  
where \(\omega_{ij}=\frac{||\mathbf{P}_{ij}||^{2}}{A^{2}}\) and the raw rotation \(R_{123}\) using [PERSON]'s 3-point minimal solver [34], similar to (15). With the raw scale and rotation solved, we can define the translation-based invariants as follows:  
**Definition 4** (Translation-based invariants). : _In addition to (22), we can derive the translation-based invariants:_  
\[I_{i}^{t}=\mathbf{Q}_{i}-s_{123}\mathbf{R}_{123}\mathbf{P}_{i}=\mathbf{t}_{ gt}+\boldsymbol{\epsilon}_{i}^{t}, \tag{29}\]  
_where \(i\in\{1,2,3\}\), \(I_{i}^{t}\) represents the translation-based invariant w.r.t. the \(i_{th}\) correspondences and \(\boldsymbol{\epsilon}_{i}^{t}\) describes its noise measurement. In known-scale cases, we directly set \(s_{123}=1\)._  
To create constraints on any two invariants \(I_{i}^{t}\) from this 3-COS, we can derive the following:  
**Proposition 4** (Constraints on \(I_{i}^{t}\)).