Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!rice!uw-beaver!fluke!ssc-vax!coy From: coy@ssc-vax (Stephen B Coy) Newsgroups: comp.graphics Subject: Re: Finding nearest point Message-ID: <3639@ssc-bee.ssc-vax.UUCP> Date: 16 Feb 91 21:19:05 GMT References: <1991Feb14.181028.7851@engin.umich.edu> <16827@accuvax.nwu.edu> Sender: news@ssc-vax.UUCP Reply-To: coy@ssc-vax.UUCP (Stephen B Coy) Organization: Boeing Aerospace & Electronics 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: >>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.