|
|
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 N-dimensional space?
> at example I have 256 9-dim. 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((a1-b1)^2 + (a2-b2)^2 + ... + (a9-b9)^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((r1-x(P,1))^2 + (r2-x(P,2))^2 + ... + (r9-x(P,9))^2).
Since sqrt is an increasing function, we can discard it so we're looking
for smallest
d'(P) = (r1-x(P,1))^2 + (r2-x(P,2))^2 + ... + (r9-x(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
|
|
