Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!hellgate.utah.edu!caen!sdd.hp.com!think.com!linus!linus!linus!mitchell From: mitchell@mitre.org (Richard B. Mitchell) Newsgroups: comp.graphics Subject: Re: Finding nearest point Message-ID: Date: 15 Feb 91 20:39:28 GMT References: Sender: news@linus.mitre.org (News Service) Organization: Mitre Corporation, Bedford, MA. Lines: 39 In-Reply-To: kadie@cs.uiuc.edu's message of 13 Feb 91 18:01:22 GMT Nntp-Posting-Host: clouseau.mitre.org 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? 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