Before revision:  The main contribution of this work is a {\em trie}-based data structure that is space efficient and supports 8-approximate nearest bottleneck queries in O(-\lg(d_B( D ,Q)) \min(m, 10 ^n) n\lg^3 n ) time, where d_B( D ,Q) is the minimum bottleneck distance from Q to any point set in D. A direct consequence, of independent interest, is a simple O(-\lg(d_B(P,Q)) n \lg^3 n) time algorithm to 2 \sqrt{2 .
After revision:  The main contribution of this work is a {\em trie}-based data structure finds a 6-approximate nearest neighbor in O(-\lg(d_B( D ,Q)) \min(m, 10 ^n) n\lg^3 n ) time, where d_B( D ,Q) is the minimum bottleneck distance from Q to any point set in D. A direct consequence, of independent interest, is a simple O(-\lg(d_B(P,Q)) n \lg^3 n) time algorithm to 2 \sqrt{2 .