8
$\begingroup$

Given a set of N points in D dimensional space. How would you find the symmetry group of these points? i.e. the group of Euclidean symmetries that map the points to themselves.

To make things harder, perhaps you only know the coordinates of the points to within an accuracy of $\epsilon$.

For example, the points could be corners of a cube in 3D or corners of a hexagon in 2D.

I presume you would start with trying to find all the possible rotations and reflections. (How would you do that systematically) And then seeing how they compose.

I wouldn't need to know the name of the symmetry group perhaps just its size and a way to distinguish it from another symmetry group of the same size.

$\endgroup$
3
  • $\begingroup$ A), I don't think you need to make the problem harder :) B), I'm fairly sure that such a symmetry group is generated by reflections, so that if you could find all reflections, you could simply compose them and get rotations for free. C), Any such reflection must occur through a plane containing the midpoint of the line segment connecting a pair of points, and which is perpendicular to that edge. I think that would be enough to find the group in ideal conditions, but maybe a more confident person can say a bit more $\endgroup$
    – pjs36
    Mar 31, 2018 at 3:53
  • 1
    $\begingroup$ Good point about reflections. I think it would still be quite tricky in higher dimensions. In N dimensions perhaps the reflective "plane" should go through (N-1) points and the center. What about chiral symmetries? $\endgroup$
    – zooby
    Mar 31, 2018 at 4:13
  • $\begingroup$ You’re right, there are sets of points (convex even, I believe) which have rotational but no reflectional symmetries — so my procedure definitely won’t find all symmetries of all point sets. I still think each reflection (hyper-)plane is orthogonal to a line segment connecting some pair of points (as a naive, brute-force starting point), but, clearly, I am capable of being wrong $\endgroup$
    – pjs36
    Mar 31, 2018 at 4:52

1 Answer 1

3
$\begingroup$

In a C.S. oriented way (I assume that the set of points is not contained in some hyperplane). I don't know the specific numbers of your problem but in my mind it seems to work for reasonable data.

  • compute the convex envelop of your set of points and denote $v_1,\dots, v_M$ the set of vertices of the convexe envelop,

  • compute the isobarycenter $0$ of the points and identify the points to a vector space using $0$. Each point of your set is identified to a vector $v_i$.

  • Make the list of lengths $\|v_i\|$ for and order it. From now on we assume that $\| v_1\|\leq \dots \leq \|v_M\|$.

  • Choose arbitrarily $D$ points $v_1,\dots, v_D$ amongst the $M$ points such that they span the $D$-dimensional vector space.

  • An isometry fixing globally your set of points must send a vertex to a vertex of the same length. Therefore try all possibilities (brute force) for the images of $v_1,\dots, v_D$ and test if it gives you an invertible linear transformation and if they fix globally the set of points (maybe try first with the set of vertices).

What you get at the end is a bunch of invertible $d$ by $d$ matrices that fix globally your set. It is easily adaptable with the $\epsilon$ accuracy.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .