Snip!t from collection of Alan Dix

<h2><a name="SECTION00052000000000000000"> Approximate box decomposition trees</a> </h2> <p> Arya et al. [<a href="node21.html#Arya_1998">4</a>] 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 <img src="img1.png" alt="$ k$" align="bottom" border="0" height="14" width="13">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 <img src="img1.png" alt="$ k$" align="bottom" border="0" height="14" width="13">d-tree is able to make this assurance, but quadtrees show this characteristic [<a href="node21.html#Arya_1998">4</a>]. The actual box decomposition search tree is composed of splits and shrinks. Fig. <a href="#epsilonApx"><img alt="[*]" src="file:/usr/share/latex2html/icons/crossref.png" align="bottom" border="1"></a> (c) shows the general structure and Fig. <a href="#bd_tree"><img alt="[*]" src="file:/usr/share/latex2html/icons/crossref.png" align="bottom" border="1"></a> presents two slices within this search tree.</p>