Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!ukc!acorn!dseal
From: dseal@armltd.uucp (David Seal)
Newsgroups: comp.graphics
Subject: Re: Finding nearest point
Message-ID: <5337@acorn.co.uk>
Date: 22 Feb 91 12:24:00 GMT
References: <640001@hplvec.LVLD.HP.COM>
Sender: uucp@acorn.co.uk
Distribution: comp
Organization: Acorn Computers Ltd, Cambridge, England
Lines: 93

In article <640001@hplvec.LVLD.HP.COM> kwb@hplvec.LVLD.HP.COM (Keith
Blackwell) writes:

>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 is correct for the 2-dimensional case, and almost so for the
3-dimensional case. The general answer is that for a D-dimensional minimum
distance search, step 3 should be:

   3) then compute x^2 + y^2 + z^2 for all points whose Manhattan distance
      is within (D^(1/2)) times the smallest Manhattan distance (found in
      step 2).

As Keith says, we want to find smallest the diamond/octahedron/
higher-dimensional analogue (which I will call a hyperdiamond - not knowing
the correct terminology :-)) that contains the circle/sphere/hypersphere
with radius SMD. It is fairly clear that this diamond/octahedron/
hyperdiamond touches the circle/sphere/hypersphere at points where all three
co-ordinates have the same magnitude.

I.e. in 2 dimensions, the diamond touches the circle at four points with
co-ordinates (+/-Z,+/-Z) for some value of Z. To determine this value of Z,
we know that the Euclidean distance to this point is SMD. So Z^2 + Z^2 =
SMD^2, i.e. Z = SMD * 2^(-1/2). The Manhattan distance to this point is:

   Z + Z = Z * 2 = SMD * 2^(-1/2) * 2 = SMD * 2^(1/2)

In 3 dimensions, the diamond touches the circle at eight points with
co-ordinates (+/-Z,+/-Z,+/-Z) for some value of Z. To determine this value
of Z, we know that the Euclidean distance to this point is SMD. So Z^2 + Z^2
+ Z^2 = SMD^2, i.e. Z = SMD * 3^(-1/2). The Manhattan distance to this point
is:

   Z + Z + Z = Z * 3 = SMD * 3^(-1/2) * 3 = SMD * 3^(1/2)

In 4 dimensions, the diamond touches the circle at sixteen points with
co-ordinates (+/-Z,+/-Z,+/-Z,+/-Z) for some value of Z. To determine this value
of Z, we know that the Euclidean distance to this point is SMD. So Z^2 + Z^2
+ Z^2 + Z^2 = SMD^2, i.e. Z = SMD * 4^(-1/2). The Manhattan distance to this point
is:

   Z + Z + Z + Z = Z * 4 = SMD * 4^(-1/2) * 4 = SMD * 4^(1/2)

The pattern should now be clear.

David Seal
dseal@acorn.co.uk

Standard disclaimers apply


Brought to you by Super Global Mega Corp .com