STUDI • MARIANO TOMATIS ANTONIONO

TORNA ALL'INDICE

Analysis of alignments in R-Environment - How to find all alignments

A DETAILED GUIDE TO THE GEOMETRICAL STUDY OF SACRED GEOMETRIES AND ORTHOTENY • JULY 20, 2007

With functions #3 and #4 it is not difficult to scan a set of points in order to find all the alignments. The problem is to optimize the scanning procedure, because the "brute force" approach is not the best one. The complexity of any "brute force" algorithm would be exponential; some facts will help in the definition of the best algorithm:

1) A set of N points generates at least N*(N-1)/2 "trivial" alignments of two points.

2) If M points are aligned, the same set represents a number of M alignments of M-1 points. (For example: 4 points aligned A,B,C,D represent also 4 alignment of three points each: A,B,C and A,B,D and A,C,D and B,C,D)

By these two points we can define an algorithm with quadratic complexity:

1) Define a set of alignments of 2 points by using all the possible N*(N-1)/2 pairs of points;
2) In order to look for all the alignments of 3 points, for each of the N*(N-1)/2 alignments of 2 points verify if any of the other points are aligned with the 2. All the points aligned to each pair generate a 3 points alignment.
3) In order to look for all the alignments of 4 points, for each of the M alignments of 3 points (found at step 2) verify if any of the other points are aligned with the 3. All the points aligned to each pair generate a 4 points alignment.
...
N) The algorithm stops when no N+1 points alignment is found.

A useful trick can be added: in order to define the alignments to be tested, I have to create an array of points. Thanks to the property of "commutativity" of the points verified with the function aligned - and in order to avoid a double verification of the same set of points shuffled (for example 1,2,3 and 3,1,2) - whenever I define a set of points, I limit myself to the sorted one (so I will verify only the set 1,2,3).

Note that this can be performed only because we use Definition #3 or Definition #4: "commutativity" is not a property of Definition #1 and #2!

Please, download the complete R file from here find_all.txt: you can test it on R-Environment.

© 2017 Mariano Tomatis Antoniono