How to perform a sum of least squares/regression?

I’m working on an ICP(iterative closest point) algorithm and am stuck at the point of finding the matching points where the sum of their distances squared is minimized.

I’m not sure of the right method and how to use it.

Essentially, I have two XYZ point sets of size M and N respectively and have computed the Euclidean distances between each point in each set. Next, where I’m stuck, is to find the pair of points such that the sum of distances squared is minimized.

I expect a result of paired points of size M.

Any tips/support is appreciated.

All I know about ICP is what I read in the Wikipedia page for “iterative closest point”. If I follow correctly, the suggestion there is to use a “k-d tree” algorithm, about which I also know nothing except that there is a Wikipedia page for that as well.

I’ll note that ICP page has pointers to several open source implementations of ICP so maybe you can learn from one of those.

From my own experience, I would say that since the algorithm you want is just choosing things, you might be able to use an integer linear program. It’s easy for an ILP get so big it’s not feasible to solve in a reasonable time, but a quick method like the Steppingstone algorithm might work. This approach would not include the statistical tests for outliers, etc that might be might be wanted.