
Re: Searching the nearest point
Posted:
Dec 10, 1996 12:10 PM


Robert Spalek <robert@atrey.karlin.mff.cuni.cz> wrote in article <5840qo$rto$8@ns.felk.cvut.cz>... > do you know a fast algorithm for searching the nearest point from given set > in Ndimensional space? > at example I have 256 9dim. points and want to find the nearest of them > to find an aproximation
In the following I will assume that by "nearest" you mean "the smallest Euclidean distance", calculated as
d = sqrt((a1b1)^2 + (a2b2)^2 + ... + (a9b9)^2),
where sqrt means square root, first point is denoted as a = (a1,a2,...,a9) and second point as b = (b1,b2,...,b9). I will use constants (256 and 9, as in your example) for better readability.
Denote the points in your set as
x1 = (x(1,1), x(1,2), x(1,3), ..., x(1,9)) x2 = (x(2,1), x(2,2), x(2,3), ..., x(2,9)) . . x256 = (x(256,1), x(256,2), ..., x(256,9)).
Denote the reference point, to which you are trying to find the closest one in the set as
r = (r1, r2, r3, ..., r9).
So, what we are looking for is the point P in the set, that has the smallest value of
d(P) = sqrt((r1x(P,1))^2 + (r2x(P,2))^2 + ... + (r9x(P,9))^2).
Since sqrt is an increasing function, we can discard it so we're looking for smallest
d'(P) = (r1x(P,1))^2 + (r2x(P,2))^2 + ... + (r9x(P,9))^2
which translates to
d'(P) = r1^2  2*r1*x(P,1) + x(P,1)^2 + ... + r9^2  2*r9*x(P,9) + x(P,9)^2.
Since the r1, ..., r9 are the same for all P we can discard their squares too. The nature of problem suggests that you might want to use the same set of points many times. If so, it is a good idea to precalculate the sum of squares of coordinates for each point separately and store it, say in S(P). That way we have
d''(P) = S(P)  2*(r1*x(P,1) + ... + r9*x(P,9)).
Recall that we are looking for the smallest d''(P). The algorithm is now trivial (in a pseudo C):
// precalculate S(P) in case you use the same set many times for(i=1;i<256;i++) { S(i)=0; for(j=1;j<=9;j++) S(i)+=x[i][j]^2; }
closest_point=0; closest_distance=maxnumber; for(i=1;i<256;i++) { c=0; for(j=1;j<=9;j++) c+=r[j]*x[i][j]; d''=S(i)2*c; if(d''<closest_distance) { closest_distance=d''; closest_point=i; }; }
Retrospectively, we discarded sqrt, some additions and possibly saved some time using precalculation for each point. I hope it helps to some extent.
Regards, Mitja Kolsek

