Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!think.com!snorkelwacker.mit.edu!shelby!unix!hplabs!hpfcso!hplvec!kwb
From: kwb@hplvec.LVLD.HP.COM (Keith Blackwell)
Newsgroups: comp.graphics
Subject: Re: Finding nearest point
Message-ID: <640001@hplvec.LVLD.HP.COM>
Date: 20 Feb 91 02:08:24 GMT
References:
Organization: Hewlett-Packard Co., Loveland, CO
Lines: 51
I'm no mathematician, but I believe the following (quoted from a post
by Richard B. Mitchell) is very much WRONG:
| 1) For all of the points in the set, compute the manhatan
| distance ( delta x + delta y + delta z).
| 2) Choose the one with the smallest manhatan distance.
| 3) then compute x^2 + y^2 + z^2 for all points whose
| Manahtan distance is within 1/(2^ (1/2)) of the point from
| #2.
| 4) choose the smallest from the set in #3.
however, it is close. Consider this quoted explanation in the case
where the closest point is the point with the smallest "manhatan" distance:
| ... however the closest point will have a manhatan distance
| which is <= 1/(2^ (1/2)) * the smallest manhatan distance. ....
This statement then becomes (using "m" for manhatan distance):
m <= m / sqare_root_of_two
which is obviously false since the square_root_of_two is > 1!
I believe the problem comes in dividing by the square_root_of_two when
you should actually be multiplying.
Now let me offer my understanding of this by describing it in 2 dimensional
terms rather than 3D terms (draw this on paper for clarity):
When you find the [point with] the smallest manhatan distance (let me call
that MD for short) from the search point, you actually find a diamond about
that search point. That is, all points with a given MD about the search
point form a diamond about that search point, with diagonals of length
2 * MD.
We can now say that the closest point must lie within the smallest
circle CONTAINING that diamond. So we need only examine points within
that containg circle, which has radius equal to the smallest MD (SMD).
But to get the circle would require euclidian distance, and we want
to use the MD's we just calculated. So we simply look within the diamond
that CONTAINS that circle. And guess what MD that diamond has?
All points within the smallest diamond containing the smallest circle
that contains the diamond represented by the smallest MD (SMD) will have
an MD that is <= SMD * square_root_of_two.
So the original post suggested dividing by the square root of two where you
should be multiplying. Thus step # 3 should be reworded:
3) then compute x^2 + y^2 + z^2 for all points whose
Manhatan distance is within (2^ (1/2)) times the
smallest Manhatan distance (found in #2).
This seems clear to me. If I'm wrong PLEASE CORRECT ME! (I may use
this myself :-) I didn't want to be silent on this, lest someone mistakenly
use it (assuming my criticism is valid).
--
Keith Blackwell (my employer has nothing to do with this)