Günter Rote:

Partial least-squares point matching under translations

In: 26th European Workshop on Computational Geometry (EuroCG'10), Dortmund, March 2010, pp. 249–251, Editor: Jan Vahrenhold.


We consider the problem of translating a given pattern set B of size m, and matching every point of B to some point of a larger ground set A of size n in an injective way, minimizing the sum of the squared distances between matched points. We show that when B can only be translated along a line, there can be at most m(n - m) + 1 different matchings as B moves along the line, and hence the optimal translation can be found in polynomial time.

  slides of the talk   pdf file (gzipped)
other papers about this subject
Last update: April 12, 2010.