Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!helios!binoc!antek
From: antek@binoc.tamu.edu (Antek Laczkowski)
Newsgroups: comp.graphics
Subject: The closest point. Suggestions.
Summary: Proposals for finding the nearst point
Message-ID: <12449@helios.TAMU.EDU>
Date: 21 Feb 91 19:22:40 GMT
References: <1991Feb21.181630.3627@magnus.ircc.ohio-state.edu>
Sender: usenet@helios.TAMU.EDU
Organization: Texas A&M University, College Station
Lines: 47

Hi!   This is my 2 cents in the "How to find the point closest to a given one"
      discussion.

1) I wouldn't use one and only one algoritm - rather vary the method
depending of : How many points at all have you to deal with ? Are the points
fixed or may change their locations ?  How fast is FP aritmetic comparing to
INTEGER ? etc. 

2) Let me first give a quick algoritm for points in 2 or 3 D. If you can keep
their coordinates as integers, it should be quick, because only "+ - if abs"
are involved. The "Manhatan distance" has its usual meaning.

   a) Let the current point be "P". 
   b) Find the closest point(s) in the meaning of the "Manhatan" distance.
      Note, you may compare x,y,z coordinate differences separately to the
      previous "minimum" to speed up the process.
   c) If there is ONLY ONE "closest" point - it is also the closest in the
      terms of "normal" (i.e. Pitagorean (?)) distance. End.
      If there is MORE points, store them in a list. Go to "d".
   d) For each point from the list (for which you also stored the differences
      in coordinates to "P": (dx,dy,dz) calculate: 
        In 2-D space: ABS(dx - dy)
        In 3-D space: ABS(dx - dy) + ABS(dx - dz) + ABS(dy - dz)
      The point(s) for which the above is minimal is the closest one. End.

(Write to Antek @ Bioch.Tamu.Edu for a proof). As you see,  NO MULTIPLICATIONS
are involved, in the integer math it should run fast.

3) If you have a fixed set of points and need the "closest one" frequently,
maybe it is better to pre-calculate a list of "closest point(s)" for each one?

4) If the number of points is huge, I would suggest to group them in "clusters"
- you don't need a separate array for it, just run once through them and order
them in separate lists for each "cluster" basing on xyz coordinates. Then you
may search only a few clusters for the closest point. Of course if you are
searching for the "closest one" few times (like log(N) times, N=the number of
points) - "ordering" will take longer than an ordinary search. The "clustering
process" has even more sense if you may control the coordinates of each point
from the begining - the "ordering" operation requires only the time ~ N. 

5) For some particular problems when you KNOW where the points should be 
   (for example on a circle, in 1 plane, etc. ift is really worth to use some
   math and reduce the dimension of the problem - it should speed up searching.

Antek @ Bioch.Tamu.Edu  ("R" may NOT work, "Binoc.Tamu.Edu has problems with
                          mail !!")
=============================================================================


Brought to you by Super Global Mega Corp .com