Multidimensional binary search trees
in [Theory]
|
From: Babua on 18 Apr 2007 00:46 On Apr 17, 6:20 pm, king...(a)freemail.it wrote: > On 17 Apr, 13:09, Babua <pin...(a)iitg.ernet.in> wrote: > > > > > > > On Apr 17, 2:29 pm, king...(a)freemail.it 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?- Hide quoted text - > > - Show quoted text - You can get details about higher order voronoi diagrams from any Computational Geometry standard text. The only problem here is the the preprocessing step. For 2d problem you can use planar point location preprocessing. But in higher dimensions the combinatorial complexity of higher order voronoi diagrm may be large. Like the combinatorial complexity of 1st order Voronoi diagram is O(n^2) in 3D. Of course you can superimpose an orthogonal d-dimensional grid over the structure and do the preprocessing to answer the query. But the approach may not be very efficient. Thanks. --- Pinaki ============================================================
From: mayur on 18 Apr 2007 05:02
On Apr 17, 2:29 pm, king...(a)freemail.it 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 > 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. kd-trees are good for nearest-neighbour queries in the approximate sense. There's a paper on approximate nearest-neighbour searching using kd-trees. http://theory.stanford.edu/~rinap/papers/nnsqualpods.ps Also look at this standard text-book description: - http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK4/NODE188.HTM thanks, mayur |