# comp.graphics.algorithms

## Subject: Re: nearest neighbour of a point

Michael Hennebry wrote:
> Gino van den Bergen wrote:

>>>
>> 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?
>

Hard to say. It is best to experiment with the cell size. I suppose that
not all of the 50 dimensions are very significant if one only has a
million samples. I would reduce the hash to the 5 to 10 most significant
axes, and start with a cell size of one tenth of the total space size.

Gino