Re: nearest-neighbors calcs

• To: Rick Wayne <fewayne@xxxxxxxx>
• Subject: Re: nearest-neighbors calcs
• From: Bill Hibbard <billh@xxxxxxxxxxxxx>
• Date: Fri, 31 Oct 2003 17:45:48 -0600 (CST)

Hi Rick,

> i have a data-centric app (i.e., no visualization, sadly), but part of
> what it needs to do is take two 3D data sets (float x, float y, float
> value) and construct a set of tuples, each of which contains an element
> in data set 1, and the elements in data set 2 that are closer to it than
> to any other point in data set 1.

This is a somewhat non-standard computation. For each point
in set 1, you need to compute the distance to the nearest
other point in set 1. Then find all points in set 2 within
that distance.

>  i'd prefer to adopt an existing data model rather than write my own,
> and of course visad came to mind.
>
> something, somewhere in the code knows how to do nearest-neighbor calcs
> for interpolation; i don't see anything about voronoi diagrams, but
> there's delaunay class hierarchy, so i'm at least partway there.

VisAD can make it easy to find the point from set 2 that is
closest to a given point in set 1, which is a pretty standard
thing to do for interpolation. To do this, you'd construct an
Irregular2DSet (assuming you are interested in 2-D distances
using x and y) from set 2, then pass the points in set 1 to
the valueToIndex() method of that Irregular2DSet. But what you
want is a bit unusual.

> has anybody done this kind of thing with the visad data model? or can
> you suggest another avenue i should take?
>
> i do have an out: the data sets are small enough (say, 20 in one and
> 25,000 in the other) that brute force will serve -- i can compute
> 500,000 euclidean distances and sort them out in a few seconds. but that
> would be aesthetically displeasing!

Probably easiest to just do this.

Good luck,
Bill

• References:
  • nearest-neighbors calcs
    • From: Rick Wayne