Nearnest points

Nearnest points

Post by Dmytry Lavr » Mon, 30 Jun 2003 23:11:54



Dear All,
i'm searching for fast algorithm to find nearest point for every point
in set of points(;-) ,Euclidian space(2D or 3D), in time O(n*log(n))
or faster.

First idea i got is "Divide&Conqirer"(or "divide skin of non-killed
bear";-)
:Split set of points into 2 sets,find nearnest points and distance to
splitting line in each subset(recursively to trivial case),and for all
points with distance to line lesser than distance to nearest point
check if nearest point are in another subset.Second (bad)idea is to
sort points by "xyzxyzxyzxyz" bit mixing...

Is here another algorithms avaliable?(or where i can find more
information?)
What are faster for case when points are randomly allocated? when in
small randomly allocated groups?

Also i'm looking for similar algorithm to find intersecting lines.

Thanks in advance,

Dmytry,
http://dmytrylavrov.narod.ru

 
 
 

Nearnest points

Post by Hans-Bernhard Broeke » Tue, 01 Jul 2003 02:39:25



> :Split set of points into 2 sets,find nearnest points and distance
> to splitting line in each subset(recursively to trivial case),and
> for all points with distance to line lesser than distance to nearest
> point check if nearest point are in another subset.Second (bad)idea
> is to sort points by "xyzxyzxyzxyz" bit mixing...

These algorithm ideas are re-inventions of known ones (of course).

One is the binary space partitioning approach in one of it's variants
(octree, BSP tree, k-d trees), which can indeed be used to reduce the
average runtime of neighbour searches considerably.  The problem is
that worst-case behaviour doesn't necessarily improve in the same way.

The second one is a mix of hash tables and implicitly coded octree
cell indices used for the same purpose.  It's not actually bad at all,
*if* you can pull off the bit string manipulations efficientlly.  A
unified input coordinate range (say 0..255), a precomputed table and
some shift operations can work wonders in that department.

You general plan is quite valid: divide-and-conquer is exactly the
right way to tackle this.  The only real question left is how exactly
to divide.
--

Even if all the snow were burnt, ashes would remain.