From: ptitjean@ccr.jussieu.fr (Michel PETITJEAN)
Subject: Re: Point alignment problem (optimization)
Date: 10 Apr 2000 10:16:42 +0200
Newsgroups: sci.math
Summary: Best Euclidean motion to map  n  points near to  n  others?

In article: <8cqufb$ceu$1@inxs.ncren.net>
Tobias Gloth <gloth@gloth.ntwrks.com> wrote:
>Given two sets P and Q of n points (elements of R^d), is there a
>practicable way to obtain an affine linear transformation A, such that
>
>   - the linear part of A (a d*d matrix) is orthonormal and has
>     determinant 1, i.e. A only rotates and/or moves the points, and
>   - the sum over |P_i - A*Q_i|^2, (i=1,...,n, and the distance being
>     euclidean) is minimal for all such transformations, i.e. A aligns
>     Q to P as good as possible?
>
>I'm really only trying to solve this for n=3 and d=3, but if there's
>a general solution, I'd be curious to hear that as well.
>
>    -Tobi

AFAIK, the solution is unknown when n>d>3. You can find the solution
for d=2 and d=3 in the appendices of my papers:
 J.Math.Chem 1997,22[2-4],pp.185-201
 J.Math.Phys 1999,40[9],4587-4595.
When n=d, the sets have in fact a (d-1) dimensionality. In this
situation, the Procrustes algorithme (see it in the book of Golub
and Van Loan "Matrix Computations") operates for any d, because the set
is not different from its inverted image.

Michel Petitjean,                     Email: petitjean@itodys.jussieu.fr
ITODYS (CNRS, ESA 7086)                      ptitjean@ccr.jussieu.fr