Efficient search for equilateral triangles, squares and regular pentagons in a set of 3D points

Question

For an algorithm to identify cubic point groups from a set of atom positions $r_i$ forming a molecule, I would need an efficient and fast algorithm to identify equilateral triangles, squares and regular pentagons with their vertices being the atom positions $P=\{r_i:i=1..n\}$ and $n$ being the number of vertices. These elements determine the z-axis of the coordinate system to be used to analyse the symmetry of the molecule.

A straightforward but brute-force approach is the subdivision of the point set into subsets of atom positions $S \subset P, \lvert S \rvert=m$ with $m={3,4,5}$ respectively.

The criteria for identifying the three regular polygon types are

1. Equilateral triangle(m=3): For each set S the distances $\lvert r_{ij}\rvert=\lvert r_i-r_j \rvert$ are identical.
2. Square($m=4$) and Pentagon($m=5$): For each set $S$ the centroid is calculated as $r_c=\frac{1}{k}\sum_{i=1}^{m} r_i$. Then the set $S$ is forming a square and pentagon respectively if all distances $\lvert r_{ci}\rvert=\lvert r_i - r_c \rvert$ are equal.

For case 2 we further need to test if the point sets are coplanar. This can be done by simply testing if the matrix $\begin{pmatrix}r_1\\r_2\\r_3\\\vdots\\r_m\end{pmatrix}$ is of rank 2.

Furthermore for case 2 we have to identify if the polygon is really regular (with the current test we would find rectangles and irregular pentagons too, thanks for the hint user58697 !)

Now here is my problem (besides the open issue how to distinguish between irregular and regular polygons for case 2): With the brute-force approach, for e.g the spherical $C_{60}$ molecule (the Buckminster Fullerene) consisting of 60 atoms, I end up with 34220, 487635 and 5461512 subsets to test for m=3,4 and 5 respectively. Any idea how to segment potentially the problem further to make it more tangible?

Answer 1

Do you have exact values for the co-ordinate or not?

If they are exact it is probably quicker to look at angles (or the cosine of the angle which the dot product would give). That would be 34220 calculations for the angle $(A_{abc})$ at $r_a$ between points $r_b$ and $r_c$. You can then quickly reject all but the 60°, 90° and 108° cases. Then you can try to look for loops of the required length. This will avoid having to check for coplanar. E.g. if $A_{abc}$ is 108° then you want to look for an angle like $A_{bcd}$ then $A_{cde}$ then $A_{dea}$ and finally $A_{eab}$.