The Math Forum

Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM 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 <> wrote in article
> do you know a fast algorithm for searching the nearest point from given
> 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) +

Since the r1, ..., r9 are the same for all P we can discard their squares
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


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]

© The Math Forum at NCTM 1994-2017. All Rights Reserved.