Indexing Point Sets for Approximate Bottleneck Distance Queries

10/22/2018
by   Brendan Mumey, et al.
0

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

Please sign up or login with your details

Forgot password? Click here to reset