This flashcard is just one of a free flashcard set. See all flashcards!

kD-Tree
Store photons in a balanced kD-Tree (i.e., a binary tree) with entries . The two child nodes of an inner node are and .

A balanced kD-Tree is constructed by successive median splits.

kD-Tree k-NN Search
Input:
: query point
: root node of subtree to be searched

Global variables:
: priority queue containing k-best search results
: distance from to furthest result in , or if less than results

knn(, ):
    if( is a leaf)
        insert into
        update
    else
        if is left of split plane
            knn(, )
            if distance to split plane
                knn(, )
        else
            knn(, )
            if distance to split plane
                knn(, )

More efficient: Compare squared distances