Supplementary material

On Maximum Clique and Maximum Consensus Formulations in Point Cloud Registration

Paper Lean Proofs
 Examples

Abstract

Maximum clique and maximum consensus are widely used formulations for robust point cloud registration in robotics. Maximum consensus seeks one transformation that aligns as many matches as possible, while maximum clique selects matches through pairwise distance tests. Maximum clique is often used as a substitute for or an approximation to maximum consensus, with empirical evidence suggesting a close relationship. However, how closely the two formulations agree is not fully understood. We study this relationship theoretically. We show that a maximum clique can have arbitrarily large alignment error and be arbitrarily larger than the maximum consensus set at any fixed positive tolerance, and derive geometric conditions that bound this error. When rotation is fixed, we derive sharp error bounds and tests that exactly characterize maximum consensus for the translation subproblem. Finally, we study group-kk consistency, which tests groups of kk matches, and determine the smallest group sizes that guarantee alignment error bounds independent of point cloud scale and geometry. These are d+1d+1 for rotations and translations and d+2d+2 when reflections are allowed, in dimensions d≥2d\ge2. Interactive examples and proof verification using the Lean theorem prover are available at https://ariarobotics.github.io/mc-vs-mc-registration/.

Main Results

Definitions

Maximum Consensus

Alignment Error
ρ(C)=min⁡T∈E(d)max⁡i∈C∥T(pi)−qi∥\rho(C)=\min_{T\in\mathrm{E}(d)}\max_{i\in C}\|T(p_i)-q_i\|
Maximum Consensus
MC⁡(τ)=max⁡{∣C∣:ρ(C)≤τ}\operatorname{MC}(\tau)=\max\{|C|:\rho(C)\le\tau\}

Pairwise Consistency

Pairwise Discrepancy
δij=∣∥pi−pj∥−∥qi−qj∥∣\delta_{ij}=\big|\|p_i-p_j\|-\|q_i-q_j\|\big|
Consistency Graph
E(Gϵ)={{i,j}:i<j, δij≤ϵ}E(G_\epsilon)=\{\{i,j\}:i<j,\ \delta_{ij}\le\epsilon\}
Maximum Clique
ω(Gϵ)=max⁡C clique in Gϵ∣C∣\omega(G_\epsilon)=\max_{C\text{ clique in }G_\epsilon}|C|

Local Consistency Tests

kk-Group Alignment Error
ρk(C)=max⁡I⊆C, ∣I∣≤kρ(I)\rho_k(C)=\max_{I\subseteq C,\,|I|\le k}\rho(I)
Local Consensus Bound
MC⁡k(τ)=max⁡{∣C∣:ρk(C)≤τ}\operatorname{MC}_k(\tau)=\max\{|C|:\rho_k(C)\le\tau\}

Restricted Subproblems

Translation(fixed RR)
ρ(t)(C)=min⁡t∈Rdmax⁡i∈C∥Rpi+t−qi∥\rho^{(t)}(C)=\min_{t\in\mathbb R^d}\max_{i\in C}\|Rp_i+t-q_i\|
Proper Rigid Motions
ρ+(C)=min⁡T∈SE(d)max⁡i∈C∥T(pi)−qi∥\rho^+(C)=\min_{T\in\mathrm{SE}(d)}\max_{i\in C}\|T(p_i)-q_i\|

Known rotation

Translation

Pairwise consistency

Factor 2dd+1\sqrt{\frac{2d}{d+1}}

ρ(t)(C)≤2dd+1 ρ2(t)(C)\rho^{(t)}(C)\le\sqrt{\frac{2d}{d+1}}\,\rho^{(t)}_2(C)

Jung’s bound is sharp for a regular simplex.

Higher-order consistency

First sufficient order
d+1d+1
Error factor
11
ρ(t)(C)=ρd+1(t)(C)\rho^{(t)}(C)=\rho^{(t)}_{d+1}(C)

Consistency is exact at order d+1d + 1.

Rotations without reflections

Proper rigid motions

Pairwise consistency

Unbounded

Pairwise consistency admits no dimension-only alignment-error bound.

Higher-order consistency

First sufficient order
d+1d+1
Error factor
2d+12d+1
ρ+(C)≤(2d+1) ρd+1+(C)\rho^+(C)\le(2d+1)\,\rho^+_{d+1}(C)

Order d+1d + 1 is the first with a dimension-only error bound.

Rotations and reflections

Rigid motions

Pairwise consistency

Unbounded

Both the alignment error at fixed pairwise tolerance and the clique-to-consensus ratio can be arbitrarily large.

Higher-order consistency

First sufficient order
d+2d+2
Error factor
2d2\sqrt d
ρ(C)≤2d ρd+2(C)\rho(C)\le2\sqrt d\,\rho_{d+2}(C)

Order d+2d + 2 is the first with a dimension-only error bound.

Synthetic Examples

Problem setup
Controls
Click pointShow allowed motion
Preserve edgesKeep current graph edges
Double clickSelect cloud
Shift+clickSelect points
Shift+drag/RMB dragRotate in 3D viewer

Point clouds

Source and target correspondences
SourceTargetTolerance τ\tau

Consistency graph GϵG_\epsilon

Edges indicate pairwise compatibility
Maximum cliqueMissing edge

Real-world Examples

Real scans

Loading real scans…
SourceTargetTolerance τ\tau
Selected matches—
Maximum residual—
Within τ\tau—