Indexing Point Sets for Approximate Bottleneck Distance Queries
share
The 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 ∈ 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 trie-based data structure that is space efficient and supports 8-approximate nearest bottleneck queries in O(-(d_B(D,Q)) (m,10^n) n ^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(-(d_B(P,Q)) n ^3 n) time algorithm to 2 √(2)-approximate d_B(P,Q), for any two point sets P and Q. Finally, the querying algorithm proposed is easily adapted to support nearest subset and superset queries.
READ FULL TEXT