text: 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 @math planar point sets (of varying sizes) to create a database @math that supports nearest bottleneck distance queries: given a query point set @math of size @math , the point sets @math 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 @math in the plane. The main contribution of this work is a trie -based data structure that is space efficient and supports @math -approximate nearest bottleneck queries in @math time, where @math is the minimum bottleneck distance from @math to any point set in @math . A direct consequence, of independent interest, is a simple @math time algorithm to @math -approximate @math , for any two point sets @math and @math . Finally, the querying algorithm proposed is easily adapted to support nearest subset and superset queries.
  @cite_3: Abstract This paper considers the computer vision problem of testing whether two equal cardinality points sets A and B in the plane are e-congruent. We say that A and B are e-congruent if there exists an isometry I and bijection l:A → B such that dist(I(a), l(a)) ⩽ e, for all a ϵ A. Since known methods for this problem are expensive, we develop approximate decision algorithms that are considerably faster than the known decision algorithms, and have bounds on their imprecision. Our approach reduces the problem to that of computing maximum flows on a series of graphs with integral capacities.
  @cite_8: We give an O(n log3 n) algorithm that, given an n-node directed planar graph with arc capacities, a set of source nodes, and a set of sink nodes, finds a maximum flow from the sources to the sinks. Previously, the fastest algorithms known for this problem were those for general graphs.
summary: Earlier seminal work by Hefferman and Schira @cite_3 considered approximation algorithms for the more general problem in which one of the point sets is mapped by an isometry (translated, rotated, and possibly reflected) prior to being matched. In the case of just computing the bottleneck distance, their methods provide a @math time algorithm to test if @math , where the answer must be correct if @math . A key idea in @cite_3 is to check for bottleneck matchings using a maximum flow computation in graph that arises from snap-rounding'' the point sets to their nearest point in grid. Our approach uses a similar idea in which the maximum flow instance is a planar graph (not true for @cite_3 ), so a recent improved algorithm for multi-source, multi-sink maximum flow due to Borradaile @cite_8 that runs in @math time can be leveraged.