assume a list of points or nodes. each one of them has x and y coordinates . the distance between two points i and j equal D(i,j)= sqrt((xi-xj)^2+(yi-yj)^2).
now, i want to select a set of these nodes which have equal distances between them (the inter-distance is specified previously --> d). hence the selected points are uniformly distributed
You can compute the inter-point distance matrix (as you have the formula) and then select points where D(i,j) = d. The problems are twofold: this could be a very large matrix and wastes a lot storage (more on this in a minute); the second problem as you can probably imagine is the precision of the match --- what about pairs who have a distance d +/- epsilon? You can decide if you want to have a somewhat fuzzy match. So, next, instead of computing the entire distance matrix, you can proceed down the list of points (i = 1:n) and for each point i, look at its neighbors (for example all other points within a radius X of our point), and then from among those see if any are close to the distance of interest. (Actually like checking a narrow ring from i with radius d + / - epsilon. )
You could also consult some spatial data base books, like Hanan Samet.
Dear Morton, your answer is very interesting, however, I wonder about selection of a number of nodes which are separated by an equal distance from each other (d) for example points (A B C D), where AB~=AC~=AD~=BC~=BD~=CD ~=d
hence i guarantee the equal distance between all nodes
If i understand correctly you have a set of points S in R2 and you want to find a subset A of S were the euclidean distance between each one of the points is the same = d.
The maximum number of mutually equidistant points in an n-dimensional Euclidean space is (n+1).
https://www.quora.com/Is-it-true-that-there-could-be-at-most-n+1-points-that-are-mutually-equidistant-in-a-n-dimensional-space
So in your case you want to look for subsets of at most 3 points in each subset.
- Badges
- Science topic