kadie@cs.uiuc.edu (Carl M. Kadie) (02/14/91)
Given a set of 3-D data points, {<x,y,z>}, and
a point p1, <x1,y1,z1>, is there a fast way to find which
point in the set is nearest to p1?
I've tried to think of ways to sort the set, but search is
linear (and often a little slower).
--
Carl Kadie -- kadie@cs.uiuc.edu -- University of Illinois at Urbana-Champaignpong@caen.engin.umich.edu (Bryan John Jalowitz) (02/15/91)
In article <kadie.666468082@herodotus.cs.uiuc.edu> kadie@cs.uiuc.edu (Carl M. Kadie) writes: >Given a set of 3-D data points, {<x,y,z>}, and >a point p1, <x1,y1,z1>, is there a fast way to find which >point in the set is nearest to p1? > >I've tried to think of ways to sort the set, but search is >linear (and often a little slower). > This is the best way I've come up with yet. First sort the set of 3-D data points on x, then y, then z. Make the best initial guess you can given the information available to you. With no additional information you can do the following: find the closest match in x. for that value of x find the closest match in y. for that value of x and y find the closest match in z. (It's not always a great guess, but it's a place to start.) Calculate the error from that guess to your point p1. The exact error is the Euclidian distance. A faster way at the expense of a little accuracy is described in Graphics Gems by Glassner (see the FAQ) in the article "A Fast Approximation to 3D Euclidian Distance". From this point traverse both up and down your 3D set keeping track of the point with the minimum error. Stop when the error in x exceeds the minimum error found. >-- >Carl Kadie -- kadie@cs.uiuc.edu -- University of Illinois at Urbana-Champaign Tony Whipple Tony_Whipple@um.cc.umich.edu
kadie@cs.uiuc.edu (Carl M. Kadie) (02/16/91)
In <kadie.666468082@herodotus.cs.uiuc.edu> kadie@cs.uiuc.edu (Carl M. Kadie) writes: >Given a set of 3-D data points, {<x,y,z>}, and >a point p1, <x1,y1,z1>, is there a fast way to find which >point in the set is nearest to p1? >I've tried to think of ways to sort the set, but search is >linear (and often a little slower). I've received many helpful replies. Many people recommend the book "Computational Geometry" by Preparata and Shamos. And a book by Herbert Edelsbrunner. (Coincidental, Preparata and Edelsbrunner have offices upstairs of mine) -- Carl Kadie -- kadie@cs.uiuc.edu -- University of Illinois at Urbana-Champaign
mitchell@mitre.org (Richard B. Mitchell) (02/16/91)
In article <kadie.666468082@herodotus.cs.uiuc.edu> kadie@cs.uiuc.edu (Carl M. Kadie) writes: >Given a set of 3-D data points, {<x,y,z>}, and >a point p1, <x1,y1,z1>, is there a fast way to find which >point in the set is nearest to p1? Here is one solution that I came up with 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. What this does essentially is eliminate computing the distance for all of the points. Since addition is cheap, computing the manhatan distance is inexpensive. Once you have the point which has the shortest manhatan distance, you are not guarenteed that it is the closest point, however the closest point will have a manhatan distance which is <= 1/(2^ (1/2)) * the smallest manhatan distance. Also, you need not do the square root to determine the closest point. Square roots are expensive and omitting this will save time and not cause any errors. -- ------------------------------------------------------------------------------- Richard B. Mitchell mitchell@linus.mitre.org M/S A047 The Mitre Corp. (617) 271-8390 Burlington Rd Bedford MA 01730
kaufman@delta.eecs.nwu.edu (Michael L. Kaufman) (02/16/91)
In article <1991Feb14.181028.7851@engin.umich.edu> pong@caen.engin.umich.edu (Bryan John Jalowitz) writes: >In article <kadie.666468082@herodotus.cs.uiuc.edu> kadie@cs.uiuc.edu (Carl M. Kadie) writes: >>Given a set of 3-D data points, {<x,y,z>}, and a point p1, <x1,y1,z1>, is >>there a fast way to find which point in the set is nearest to p1? >>I've tried to think of ways to sort the set, but search is >>linear (and often a little slower). >This is the best way I've come up with yet. >First sort the set of 3-D data points on x, then y, then z. [ A long complicated method deleted] I sure hope that this is a joke. On a unsorted set the time to examine every point to determine which is closest to p1 is o(n). Any attempt to sort the points will be at least o(nlogn). So the quickest way to find the closest point to p1 is to examine every other point and see which one is closest. BTW, you know that linear time is the best you can do on an unsorted set since if you come up with an algorithm that is faster then linear I can come up with a data set that it fails on. The reason for this is that for the alogithm to be faster then linear it would have to not examine some points. I can therefore come up with a data set where one of the points you don't look at is the closest one. Michael Michael Kaufman | I've seen things you people wouldn't believe. Attack ships on kaufman | fire off the shoulder of Orion. I watched C-beams glitter in @eecs.nwu.edu | the dark near the Tannhauser gate. All those moments will be | lost in time - like tears in rain. Time to die. Roy Batty
coy@ssc-vax (Stephen B Coy) (02/17/91)
In article <16827@accuvax.nwu.edu> kaufman@delta.eecs.nwu.edu (Michael L. Kaufman) writes: >In article <1991Feb14.181028.7851@engin.umich.edu> pong@caen.engin.umich.edu >(Bryan John Jalowitz) writes: >>This is the best way I've come up with yet. >>First sort the set of 3-D data points on x, then y, then z. >[ A long complicated method deleted] >I sure hope that this is a joke. On a unsorted set the time to examine every >point to determine which is closest to p1 is o(n). Any attempt to sort the >points will be at least o(nlogn). >So the quickest way to find the closest point to p1 is to examine every other >point and see which one is closest. Don't be so quick to criticize. When I first saw the original posting I thought Hmm.. here's someone looking for a faster way to map a 24-bit image onto a fixed palette. An always popular topic on comp.graphics. In such a case the cost of doing the sort is almost zero compared to the cost of matching up to a million pixels with the appropriate palette entrys. The algorithm presented will help speed up this process quite a bit compared to the brute force approach you suggest. Stephen Coy uw-beaver!ssc-vax!coy aka coy@ssc-vax.UUCP Deep down inside I'm really quite shallow.
pong@caen.engin.umich.edu (Bryan John Jalowitz) (02/19/91)
In article <16827@accuvax.nwu.edu> kaufman@delta.eecs.nwu.edu (Michael L. Kaufman) writes: >In article <1991Feb14.181028.7851@engin.umich.edu> pong@caen.engin.umich.edu >(Bryan John Jalowitz) writes: >>In article <kadie.666468082@herodotus.cs.uiuc.edu> kadie@cs.uiuc.edu (Carl M. >Kadie) writes: >>>Given a set of 3-D data points, {<x,y,z>}, and a point p1, <x1,y1,z1>, is >>>there a fast way to find which point in the set is nearest to p1? >>>I've tried to think of ways to sort the set, but search is >>>linear (and often a little slower). > >>This is the best way I've come up with yet. >>First sort the set of 3-D data points on x, then y, then z. >[ A long complicated method deleted] > >I sure hope that this is a joke. On a unsorted set the time to examine every >point to determine which is closest to p1 is o(n). Any attempt to sort the >points will be at least o(nlogn). > Perhaps I didn't mention that this is for cases when you must search the space many times. You can sort the space once and save it. > > >Michael Kaufman | I've seen things you people wouldn't believe. Attack ships on > kaufman | fire off the shoulder of Orion. I watched C-beams glitter in > @eecs.nwu.edu | the dark near the Tannhauser gate. All those moments will be > | lost in time - like tears in rain. Time to die. Roy Batty Tony Whipple Tony_Whipple@um.cc.umich.edu
spencer@eecs.umich.edu (Spencer W. Thomas) (02/20/91)
If indeed you're trying to map RGB colors to representatives, then I've got code for you. It's part of the Utah Raster Toolkit (3.0, patch level 2, see FAQ posting for retrieval info), and can be found in the subroutine lib/inv_cmap.c. It quantizes the input data (typically to 5 or 6 bits) and builds a NxNxN (where N=2^5 or 2^6, typically) cube. You use the quantized color to index this cube, and immediately get the nearest color (up to the quantization limit). I'm working on making it do better with colors that are closer together than the quantization cell size. Apple has a similar scheme they use in Color Quickdraw, but their inverse colormaps are far from optimal. It's faster than my method, though. Where I might take 12 seconds to build a 2^5^3 inverse map, they take only about 1 second (but 2^5 is the largest they will go). -- =Spencer W. Thomas EECS Dept, U of Michigan, Ann Arbor, MI 48109 spencer@eecs.umich.edu 313-936-2616 (8-6 E[SD]T M-F)
kwb@hplvec.LVLD.HP.COM (Keith Blackwell) (02/20/91)
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)
dseal@armltd.uucp (David Seal) (02/22/91)
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
kwb@hplvec.LVLD.HP.COM (Keith Blackwell) (03/01/91)
| 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: Thanks for the correction to my correction. I should have pointed out that I didn't even attempt to expand my analysis to 3 or more dimensions since my interest in this whole issue was a two-dimensional application I am currently dealing with. Funny thing, though, my first thought upon reading the original post was "should'nt it be cube-root instead of square-root?", which of course was also wrong, but it was based on the right intuitive hunch. When I got around to analyzing the thing, though, I found the problem was (at least) in something else. Math usually just isn't so intuitive anyway :-). | David Seal | dseal@acorn.co.uk -- Keith Blackwell (my employer has nothing to do with this)
gideony@microsoft.UUCP (Gideon YUVAL) (03/07/91)
and 1976), which seem to be relevant to this discussion. -- Gideon Yuval, gideony@microsof.UUCP, 206-882-8080 (fax:206-883-8101;TWX:160520)