Re: Determine the mirror reflection relationship between the coordinates of two sets of pairs of points in n-dimension space.

[Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>]

* Hongyi Zhao [2023-03-13 00:59]:
> On Mon, Mar 13, 2023 at 2:38 AM Karim Belabas
> <Karim.Belabas@math.u-bordeaux.fr> wrote:
> >
> > Unordered sets of points then.
> 
> Very good, your general assumption above will make your algorithm
> applicable to any case of two sets of points : ordered or disordered
> correspondence between two sets of points.
> 
> > OK, so for all (a,b) with a in A and b in B,
> > compute v = a - b: this gives us the possible (unnormalized, i.e.
> > arbitrary norm instead of |v| = 1) vectors v(a,b).
> >
> > If we normalize them, the possible vectors v are the ones that occur at
> > least #A times from the (#A)^2 pairs (a,b). It should be a very short
> > list, with at most #A entries in any case. We can then check whether any
> > of the attached reflexions s work or not by computing s(A) and comparing
> > with B (as sets).
> >
> > Something like
> >
> >   normalize(v) = foreach(v, x, if (x, return(v / x)));
> >
> >   V = matreduce([normalize(a - b) | a <- A; b <-B]);
> >   for (i = 1, #V[,2], if (V[i,2] >= #A, print(V[i,1])))
> >
> > This prints the single vector
> >   v = [0, 1, -1/2, 2, 3/2, 2, -1/2, -1]~
> > with attached reflexion
> >   s(x) = x - 2 * (x~*v / norml2(v)) * v;
> >
> > Unless I made a stupid mistake, it doesn't work:
> >   ? Set([s(a) | a <- A]) == Set(Vec(B))
> >   %10 = 0
> 
> Failed as follows:
> 
[...]
> ? normalize(v) = foreach(v, x, if (x, return(v / x)));
> ? V = matreduce([normalize(a - b) | a <- A; b <-B]);
> ? for (i = 1, #V[,2], if (V[i,2] >= #A, print(V[i,1])))
> [0, 1, -1/2, 2, 3/2, 2, -1/2, -1]~
> ? s(x) = x - 2 * (x~*v / norml2(v)) * v;
> ? Set([s(a) | a <- A]) == Set(Vec(B))
>   ***   at top-level: Set([s(a)|a<-A])==Set(Vec(B))
>   ***                      ^------------------------
>   ***   in function s: x-2*(x~*v/norml2(v))*v
>   ***                   ^---------------------
>   *** _-_: forbidden addition t_VEC (8 elts) + t_COL (8 elts).
>   ***   Break loop: type 'break' to go back to GP prompt

You need to set

  v = [0, 1, -1/2, 2, 3/2, 2, -1/2, -1]~

as I wrote ! (But see below.)

> > (Please double-check, this is really a quick hack :-)
> 
> Side remark: In fact, the point sets used here are generated with
> Wolfram language, which ensure that they are mirror images of the
> other via the following commands:
[...]

Ah, so you meant an affine reflection (through a affine hyperplane with
normal vector v not necessarily containing 0; its equation being
<v,x> = c for a normal vector v as before and some scalar c, which I had
assumed to be 0).

The formula for the reflection becomes
   s_{v,c}(x) = x - 2 ((<v,x> - c) / <v,v>) * v
and everything remains the same up to (and including) the determination of
possible vectors v.

But the final check for the computed v's becomes more complicated since
we don't know c. I don't see any better way than picking a in A and
testing b - s_{v,0}(a) for all b in B. One of these b must be s_{v,c}(a)
and for this choice we must find a vector colinear to v

  s_{v,c}(a) - s_{v,0}(a) = (2 c / <v,v>) * v

giving the possible values for c (we may find other values, again a
short list: at most #A possibilities).

  s0(x) = x - 2 * (x~*v / norml2(v)) * v;
  a = A[,1]; s0a = s0(a); v = normalize(v);
  C = List();
  {
    foreach(B, b,
      if (normalize(b - s0a) == v,
        w = (b - s0a)*norml2(v)/2;   \\ c * v
        listput(C, matsolve(Mat(v), w)[1])));
  }

In this case, we find a single possibility

  ? C
  %15 = List([-5/2])

So the reflection we must now test is

  c = -5/2;
  v = [0, 1, -1/2, 2, 3/2, 2, -1/2, -1]~
  s(x) = x - 2 * ((x~*v - c) / norml2(v)) * v;

  ? Set([s(a) | a <- A]) == Set(Vec(B))
  %20 = 1

Hurray, found it !

So let's recap: the previous algorithm finds all possible v's given A,B;
for each such v, the above finds a list of tentative c and the
Set(...) = Set(...) test above is true iff s_{v,c}(A) = B (as sets)

Cheers,

    K.B.
--
Pr Karim Belabas, U. Bordeaux, Vice-président en charge du Numérique
Institut de Mathématiques de Bordeaux UMR 5251 - (+33) 05 40 00 29 77
http://www.math.u-bordeaux.fr/~kbelabas/
`