CODEWITHSUNDEEP
nearest-neighborkdtree
fred august
fred august

Reputation: 1107

Nearest neighbor search for points with directional vectors caveat

I have a set of 3D points, each of which is associated with a direction (e.g. a unit vector). Given another point + direction I would like to figure out the closest point in the set (using standard 2-norm) that also satisfies a certain condition on direction vectors (e.g. the angle between the two direction vectors is within a certain angular amount). So far I have a KD-tree based range search on the 3D points and then check whether any of such points fit within the angular constraints, but realize this is a highly unoptimized hack. Was wondering if there's an obvious better way to do this.

Many thanks in advance.

Upvotes: 3

Views: 2273

Answers (3)

Gene
Gene

Reputation: 46960

You posted long ago, but I'm working on a similar problem and found some answers, so I'll post and hope it's still of some use.

This is called in the literature constrained nearest neighbor search. This paper has a nice section on how it works on R-trees, even though the paper is about something else.

Your KD-tree is a good starting point. The algorithm in the paper for R trees will work as well for the KD-tree case.

The paper describes a specialized version of normal nearest neighbor search that's as follows.

Start by building a depth-first search that will traverse all the cells containing at least one point satisfying the caveat. The search should visit cells in order of increasing mindist from the query point. mindist is distance from query point to closest point in the cell.

Now modify the traversal to skip descent into cells with mindist larger than the best point (closest to the query and satisfying the caveat) found so far.

Upvotes: 1

John Greenall
John Greenall

Reputation: 1690

To me the main problem in your current formulation is that the angular comparison is kernelized (i.e requires a comparison between vectors). If you expand the orientation of each angle to a separate 2D vector (cos theta, sin theta) then you should just be able to do another nearest neighbour search with a limited radius in this space (KDTree should be fine) and take the intersection of the two result sets.

Upvotes: 3

Has QUIT--Anony-Mousse
Has QUIT--Anony-Mousse

Reputation: 77454

Consider using R*-trees. This data structure based on rectangles is quite amenable to complex queries.

I.e. if you can check whether a rectangle may contain points that satisfy your constraints then the R*-tree can be used to accelerate this query. The indexes in ELKI are extensible, so that may be a good starting point. From my understanding, you should be able to formulate this as a distance function in ELKI, as in this tutorial in their wiki: if the rectangle cannot satisfy the constraints, you return an infinite distance.

Upvotes: 1

Related Questions