next up previous
Next: Results Up: Approximate Data Association Previous: Approximate d-trees

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].
\includegraphics[width=27mm]{apxnn} \includegraphics[width=60mm]{bdtree}

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) \includegraphics[width=75mm,height=30mm]{tree_bd_100} (b) \includegraphics[width=75mm,height=30mm]{tree_bd_550}

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

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


next up previous
Next: Results Up: Approximate Data Association Previous: Approximate d-trees
root 2005-05-03