Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!att!pacbell.com!ucsd!casbah.acns.nwu.edu!accuvax.nwu.edu!delta.eecs.nwu.edu!kaufman From: kaufman@delta.eecs.nwu.edu (Michael L. Kaufman) Newsgroups: comp.graphics Subject: Re: Finding nearest point Message-ID: <16827@accuvax.nwu.edu> Date: 16 Feb 91 07:20:24 GMT References: <1991Feb14.181028.7851@engin.umich.edu> Sender: news@accuvax.nwu.edu Organization: EECS Department, Northwestern University Lines: 35 In article <1991Feb14.181028.7851@engin.umich.edu> pong@caen.engin.umich.edu (Bryan John Jalowitz) writes: >In article kadie@cs.uiuc.edu (Carl M. Kadie) writes: >>Given a set of 3-D data points, {}, and a point p1, , 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