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

[Hongyi Zhao <hongyi.zhao@gmail.com>]

On Mon, Mar 13, 2023 at 9:39 AM Karim Belabas
<Karim.Belabas@math.u-bordeaux.fr> wrote:
>
> * 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 !

I am glad to hear this news!

> 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)

But in all the above steps, I can only see that there is exactly one v
is found. So, the complete solution set of this problem is still not
obtained so far.

> Cheers,
>
>     K.B.

Regards,
Zhao

> --
> 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/
> `