# A Concave Optimization Algorithm for Matching Partially Overlapping Point Sets

arXiv: https://arxiv.org/abs/1701.00951 · HTML: https://mlsanity.com/paper/1701.00951/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jan 2017.

## Built on by (most cited first, 5 of 5)

- [GLAN: A Graph-based Linear Assignment Network](https://mlsanity.com/paper/2201.02057/) (2022)
- [Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets](https://mlsanity.com/paper/2101.07458/) (2021)
- [AGL-NET: Aerial-Ground Cross-Modal Global Localization with Varying Scales](https://mlsanity.com/paper/2404.03187/) (2024)
- [DC-Reg: Globally Optimal Point Cloud Registration via Tight Bounding with Difference of Convex Programming](https://mlsanity.com/paper/2603.25442/) (2026)
- [Decomposed Global Optimization for Robust Point Matching with Low-Dimensional Branching](https://mlsanity.com/paper/2405.08589/) (2024)

## Abstract (arXiv)

Point matching refers to the process of finding spatial transformation and correspondences between two sets of points. In this paper, we focus on the case that there is only partial overlap between two point sets. Following the approach of the robust point matching method, we model point matching as a mixed linear assignment-least square problem and show that after eliminating the transformation variable, the resulting problem of minimization with respect to point correspondence is a concave optimization problem. Furthermore, this problem has the property that the objective function can be converted into a form with few nonlinear terms via a linear transformation. Based on these properties, we employ the branch-and-bound (BnB) algorithm to optimize the resulting problem where the dimension of the search space is small. To further improve efficiency of the BnB algorithm where computation of the lower bound is the bottleneck, we propose a new lower bounding scheme which has a k-cardinality linear assignment formulation and can be efficiently solved. Experimental results show that the proposed algorithm outperforms state-of-the-art methods in terms of robustness to disturbances and point matching accuracy.