comp.graphics.algorithms

Subject: Re: nearest neighbour of a point

Gino van den Bergen wrote:
> Michael Hennebry wrote:
> > running.polygon@gmail.com wrote:
> >> I have 2 sets of points X & Y. The distribution of points in both the
> >> sets is such that points at a certain distance are concentrated and on
> >> either side of this distance, they start becoming sparce, something
> >> like a normal distribution. The points are in higher dimentions > 3.
> >> They may be up to 50 dimentions. Now, there are many points in each of
> >> the sets, and I would like to know if there is any efficient method to
> >> find for each point in set Y, a point in set X such that the distance
> >> between the point in set Y & the selected point in set X is <= the
> >> distance between the point in set Y and any other point in set X. I can
> >> use euclidean distance as the metric.
> >
> > This one is still unclear on how X and Y were obtained.
> >
> > I gather that X and Y are subsets of unit hypercube [0,1]^n,
> > where n is an integer that might be as large as 50.
> > Are the elements of X and Y drawn uniformly at random from the
> > hypercube?
> > If so, I expect you are stuck with an O(|X| |Y| n) algorithm.
> >
>
> Probably the simplest way of achieving subquadratic time-complexity is
> to use a spatial hash. Each point in your N-space is truncated to the
> nearest gird position of an infinite N-grid of a given cell size S. Grid
> positions are denoted by an N-vector of integers. Hashes are computed
> based on this N-vector of integers. In a spatial hash, points in
> neighboring cells of a given cell can be retrieved in constant time. By
> choosing a sensible cell size the cells can be kept relatively sparse
> (for a sort-of homogeneous distribution of points).

What is a sensible cell size and shape
if one has a million points in a unit 50-cube?