Re: Multidimensional binary search trees

kingpin@xxxxxxxxxxx writes:

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

Note that quadtrees and octrees are not binary trees but, as their
name indicates, have branching factors of 4 and 8. Generalisations to
N dimensions would have branching factors of 2^N, which make code
using them more cumbersome and some code less efficient than if a
binary tree is used.

You can make binary variants of these even for N dimensions: Each node
has two subtrees that each represent half the space.

For N=2, you would enclose the original space in an 1 x 2^(1/2)
rectangle. Each cut splits this down the middle of the longest
dimension, creating two rectangles with similar relative proportions
bu oriented differently. To get around this, you use a coordinate
transform in the recursive calls, so the longest dimension is always
X.

For N=3, you have a 1 x 2^(2/3) x 2^(1/3) box that you in each step
split along its longest dimension to create two boxes with similar
relative dimensions but different orientation, so you also here do a
coordiante transform to make X the longest dimension and Y the
second-longest.

For general N, you have an N-dimensional hyperbox with dimensions 1 x
2^((N-1)/N) x 2^((N-2)/N) x ... x2^(1/N) and do the same.

I find that you often get much shorter code using such trees than
using traditional quadtrees and octrees. The downside is that you
don't get integral bounds, so they don't work well for subdividing a
fixed grid (such as a bitmap). For for points in a space with
non-integral coordinates, they work fine.

Torben

.