Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Mitja Kolsek

Posts: 7
Registered: 12/12/04
Re: Searching the nearest point
Posted: Dec 10, 1996 12:10 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply



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







Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.