Re: Multidimensional binary search trees

On 17 Apr, 13:09, Babua <pin...@xxxxxxxxxxxxx> wrote:
On Apr 17, 2:29 pm, king...@xxxxxxxxxxx wrote:

Hi,

i've a set S of points in R^n (a vector of n real numbers, where n, in
pratical applications, is between 10 and 60). The number of points is
in the order of 10^5, 10^6. I would like organize the points in an
efficient search tree. The most important operation that i would like

You have to use mth-order Voronoi diagram for the set S. There
are different ways to compute this diagram either by lifting or
by superimposing lower order Voronoi diagrams. Also you
also have to preprocess that structure for point location query
to determine the m-nearest points of the query point P.

Thanks.

--- Pinaki

===============================================

to do is finding the nearest neighbour point (that is, give a point
P=(a1,...,ak), tell me which is the first m nearest points in the set
S to P). P does not necessarely belong to S.

For n=2,3 i know that there are quadtrees and octrees. For k>3 i've
read about kd-trees, but i'm not sure if k represents the
dimensionality of the points (that is, k = n) or the number of points
per node...

If kd-trees are suitable for a multidimensional problem, are they
efficient? Are there any other data structures that i can use to solve
the problem?
Thank you.

Can you be more specific and/or point out some references?

.