Approximate box decomposition trees

Arya et al. [4] have presented an optimal algorithm for approximate nearest neighbor search. They use a balanced box decomposition tree (bd-tree) as their primary data structure. This tree combines two important properties of geometric data structures: First, as in the $k$d-tree case, the set of points is exponentially reduced. Second, the aspect ratio of the tree edges are bounded by a constant. Not even the optimized $k$d-tree is able to make this assurance, but quadtrees show this characteristic [4]. The actual box decomposition search tree is composed of splits and shrinks. Fig. (c) shows the general structure and Fig. presents two slices within this search tree.

Figure: Left: The $(1 + \eps )$-approximate nearest neighbor. The solid circle denotes the $\eps$ environment of $\V p_g$. The search algorithm need not analyze the gray cell, since $\V p$ satisfies the approximation criterion. Middle and right: (a) Given point set. (b) decomposition into buckets. (c) Tree layout. Fig. adapted from [3,4].

Figure: A bd-tree of scanned 3D data ($k=3$) of Fig. (top) first/black 3D scan. Two $(x,y)$-projections of slices at depths $z=100$ cm (a) and $z=550$ cm are given (b).

(a)  (b) 

The search procedure of bd-trees is similar to the one of $k$d-trees. The approximate search is discontinued (cf. Fig. ) if the distance to the unanalyzed leaves is larger than

$$\norm {\V p_q - \V p}/(1+\eps ).$$