Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Topic: Searching the nearest point
Replies: 1   Last Post: Dec 10, 1996 12:10 PM

 Messages: [ Previous | Next ]
 Mitja Kolsek Posts: 7 Registered: 12/12/04
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

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

Date Subject Author
12/4/96 Robert Spalek
12/10/96 Mitja Kolsek