Path: utzoo!mnetor!tmsoft!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!caen!zeus.engin.umich.edu!pong From: pong@caen.engin.umich.edu (Bryan John Jalowitz) Newsgroups: comp.graphics Subject: Re: Finding nearest point Message-ID: <1991Feb18.163153.8315@engin.umich.edu> Date: 18 Feb 91 16:31:53 GMT References: <1991Feb14.181028.7851@engin.umich.edu> <16827@accuvax.nwu.edu> Sender: news@engin.umich.edu (CAEN Netnews) Organization: University of Michigan Engineering, Ann Arbor Lines: 29 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@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). > 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