The {\em bottleneck distance} is a natural measure of the distance between two finite point sets of equal cardinality  . In this work, we consider the problem of indexing a set of m planar point sets (of varying sizes) to create a database D that supports nearest bottleneck distance queries: given a query point set Q of size n, the point sets P \in D that are closest in terms of bottleneck distance are returned . Without loss of generality, we assume that all point sets belong to the unit box [0,1]^2 in the plane  . 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%DIFDELCMD < }%%% ^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 .
The {\em bottleneck distance} is a natural measure of the distance between two finite point sets of equal cardinality , defined as the minimum over all bijections between the point sets of the maximum distance between any pair of points put in correspondence by the bijection . In this work, we consider the problem of building a data structure \mathbb{D of m planar point sets (of varying sizes) and supports nearest bottleneck distance queries: given a query point set Q of size n, we would like to find the point set(s) P \in \mathbb{D that are closest in terms of bottleneck distance . Without loss of generality, we assume that all point sets belong to the unit box [0,1]^2 in the plane and focus on the L_\infty norm, although the techniques can also be used for other norms . The main contribution is a {\em trie}-based data structure finds a 6-approximate nearest neighbor in O(-\lg(d_B( \mathbb{D ,Q)) %DIFDELCMD < }%%% n ) time, where d_B( \mathbb{D ,Q) is the minimum bottleneck distance from Q to any point set in \mathbb{D .
A
, defined as the minimum over all bijections between the point sets of the maximum distance between any pair of points put in correspondence by the bijection
R
indexing a set
building a data structure \mathbb{D
R
to create a database D that
and
R
the point sets P \in D
we would like to find the point set(s) P \in \mathbb{D
D
are returned
A
and focus on the L_\infty norm, although the techniques can also be used for other norms
D
of this work
R
that is space efficient and supports 8-approximate nearest bottleneck queries
finds a 6-approximate nearest neighbor
R
D
\mathbb{D
D
\min(m,
D
10
R
^n) n\lg^3 n
n
R
D
\mathbb{D
R
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
\mathbb{D