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

Reply

View All Messages in

**comp.graphics.algorithms**

path:

nearest neighbour of a point =>Re: nearest neighbour of a point =>Re: nearest neighbour of a point =>Re: nearest neighbour of a point =>

Replies:

Copyright © 2006 WatermarkFactory.com. All Rights Reserved.