Arya et al. [4] have presented an optimal algorithm for approximate nearest neighbor search. They use a balanced box decomposition tree (bdtree) as their primary data structure. This tree combines two important properties of geometric data structures: First, as in the dtree 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 dtree 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.

(a)
(b)

The search procedure of bdtrees is similar to the one of dtrees. The approximate search is discontinued (cf. Fig. ) if the distance to the unanalyzed leaves is larger than