On Maximum Clique and Maximum Consensus Formulations in Point Cloud Registration

Abolfazl Babanazari; Kaveh Fathian

cs.ROOct 19, 2026

On Maximum Clique and Maximum Consensus Formulations in Point Cloud Registration

Authors: Abolfazl Babanazari, Kaveh Fathian

Organizations: Department of Computer Science, Colorado School of Mines.

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- $k$ consistency, which tests groups of $k$ matches, and determine the smallest group sizes that guarantee alignment error bounds independent of point cloud scale and geometry. These are $d+1$ for rotations and translations and $d+2$ when reflections are allowed, in dimensions $d\ge 2$ . Interactive examples and proof verification using the Lean theorem prover are available at https://ariarobotics.github.io/mc-vs-mc-registration/.

Figures & tables

Panel of Figure 1 — Fig. 1 : Maximum clique and maximum consensus can yield very different alignments. (a) Tentative feature correspondences between two 3DMatch [ 1 ] scans using FPFH [ 2 ] and mutual nearest neighbor matching. (b) Scans aligned using the ground-truth transformation, showing the inlier correspondences, maximum consensus set at tolerance $5$ cm, and maximum clique of the pairwise consistency graph at tolerance $10$ cm. (c) Fitting the maximum clique produces a poor registration despite its pairwise consistency. (d) Fitting the maximum consensus set closely aligns the scans.

Fig. 2 : Point matching followed by correspondence selection. Maximum consensus finds the transformation,

T_{2}

, that aligns the most matches within tolerance among possible transformations such as

T_{0}

T_{1}

and

T_{2}

. Maximum clique selects a largest set passing all pairwise distance tests. Group-3 consistency requires every triple in the selected set to be alignable at that tolerance, possibly by different transformations.

Panel of Figure 3 — Fig. 3 : Two reflected triangles have identical pairwise distances, forming a clique at $\epsilon=0$ . At $\tau=0.5$ , maximum consensus restricted to proper transformations can align only two matches.

Panel of Figure 4 — Fig. 4 : In the translation subproblem, pairwise consistency does not guarantee a common translation at the same tolerance. (a) Each arrow $\boldsymbol{\mu}_{i}$ is the translation vector that aligns source $\mathbf{p}_{i}$ and target $\mathbf{q}_{i}$ . (b) Every disk of radius $\tau$ centered at $\boldsymbol{\mu}_{i}$ contains all translations that align $\mathbf{p}_{i}$ and $\mathbf{q}_{i}$ within $\tau$ . Crosses mark pairwise intersections, but no translation aligns all three correspondences.

Panel of Figure 5 — Fig. 5 : Unbounded joint error at fixed pairwise discrepancy. (a) Source and target points. (b) Maximum pairwise distance error $\delta$ and alignment error $\rho$ as distance $\ell$ grows.

Fig. 6 : All six correspondences are pairwise consistent at a distance-discrepancy tolerance of

5

cm, but no triple can be aligned within

2.5

cm. Thus maximum clique has size

6

, while maximum consensus has size

2

Panel of Figure 7 — Fig. 7 : Group-3 consistency does not bound the alignment error when reflections are allowed. (a) Four correspondences forming a rectangle of width $2$ and height $\ell$ , with the two lower targets exchanged. (b) Every triple can be aligned with maximum point error at most $\sqrt{\ell^{2}+4}-\ell$ . As $\ell$ grows, this error tends to zero, while aligning all four correspondences requires error at least $1$ .

Point Cloud Registration

Point cloud registration aligns 3D point sets by estimating the transformations and correspondences that make their geometry consistent.

See all 110 papers

DC-Reg: Globally Optimal Point Cloud Registration via Tight Bounding with Difference of Convex Programming
Mar 26, 2026Wei Lian, Fei Ma, Hang Pan +2Point Cloud Registration Nonconvex Optimization
Department of Computer Science, Changzhi University, Changzhi, Shanxi, China, 046011 · School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China
Scalable and Differentiable Point-Cloud Registration Using Maximum Mean Discrepancy
Jun 26, 2026Rixon Crane, Fahira Afzal Maken, Nicholas Lawrance +4Point Cloud Registration
Data61, CSIRO, Brisbane, Australia · Data61, CSIRO, Sydney, Australia · Work done while at Data61, CSIRO, Brisbane, Australia +3
FlashReg: GPU-Accelerated 3-Clique Point Cloud Registration for Real-Time Correspondence-to-Pose Estimation
Aug 22, 2026Ziyang Yu, Xiang Li, Qiong Chang +1Point Cloud Registration Graph Matching
School of Computing Institute of Science Tokyo Tokyo

Mar 26, 2026J/K move · Enter open · S save

DC-Reg: Globally Optimal Point Cloud Registration via Tight Bounding with Difference of Convex Programming

Wei Lian, Fei Ma, Hang Pan, Zhesen Cui+1

Department of Computer Science, Changzhi University, Changzhi, Shanxi, China, 046011 · School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China

Point Cloud Registration Nonconvex Optimization Branch and Bound

Open paper AskPDF arXiv

Achieving globally optimal point cloud registration under partial overlaps and large misalignments remains a fundamental challenge. While simultaneous transformation (

\boldsymbolθ

) and correspondence (

\mathbf{P}

) estimation has the advantage of being robust to nonrigid deformation, its non-convex coupled objective often leads to local minima for heuristic methods and prohibitive convergence times for existing global solvers due to loose lower bounds. To address this, we propose DC-Reg, a robust globally optimal framework that significantly tightens the Branch-and-Bound (BnB) search. Our core innovation is the derivation of a holistic concave underestimator for the coupled transformation-assignment objective, grounded in the Difference of Convex (DC) programming paradigm. Unlike prior works that rely on term-wise relaxations (e.g., McCormick envelopes) which neglect variable interplay, our holistic DC decomposition captures the joint structural interaction between

\boldsymbolθ

and

\mathbf{P}

. This formulation enables the computation of remarkably tight lower bounds via efficient Linear Assignment Problems (LAP) evaluated at the vertices of the search boxes. We validate our framework on 2D similarity and 3D rigid registration, utilizing rotation-invariant features for the latter to achieve high efficiency without sacrificing optimality. Experimental results on synthetic data and the 3DMatch benchmark demonstrate that DC-Reg achieves significantly faster convergence and superior robustness to extreme noise and outliers compared to state-of-the-art global techniques.

Abstract

Point Cloud Registration

Explore similar work

DC-Reg: Globally Optimal Point Cloud Registration via Tight Bounding with Difference of Convex Programming

Scalable and Differentiable Point-Cloud Registration Using Maximum Mean Discrepancy

FlashReg: GPU-Accelerated 3-Clique Point Cloud Registration for Real-Time Correspondence-to-Pose Estimation