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_7: Motivated by a crane assignment problem, we consider a Euclidean bipartite matching problem with edge-crossing constraints. Specifically, given n red points and n blue points in the plane, we want to construct a perfect matching between red and blue points that minimizes the length of the longest edge, while imposing a constraint that no two edges may cross each other. We show that the problem cannot be approximately solved within a factor less than 1:277 in polynomial time unless P = NP. We give simple dynamic programming algorithms that solve our problem in two special cases, namely (1) the case where the red and blue points form the vertices of a convex polygon and (2) the case where the red points are collinear and the blue points lie to one side of the line through the red points.
  @cite_2: Let G = G(A∪B,A×B), with |A| = |B| = n, be a weighted bipartite graph, and let d(·,·) be the cost function on the edges. Let w(M) denote the weight of a matching in G, and M* a minimum-cost perfect matching in G. We call a perfect matching M c-approximate, for c ≥ 1, if w(M) ≤ c · w(M*). We present three approximation algorithms for computing minimum-cost perfect matchings in G. First, we consider the case when d(·,·) is a metric. For any Δ > 0, we present an algorithm that, in O(n2+Δ log n log2(1 Δ)) time, computes a O(1 Δα)-approximate matching of G, where α = log3 2 ≈ 0.631. Next, we assume the existence of a dynamic data structure for answering approximate nearest neighbor (ANN) queries under d(··). Given two parameters e, d e) is the query and update time of an (e 2)-ANN data structure. Finally, we present an algorithm that works even if d(·,·) is not a metric but admits an ANN data structure for d(·,·). In particular, we present an algorithm that computes, in O(e---1n3 2τ (n, e) log4(n e) log Δ) time, a (1 + e)-approximate matching of A and B; here Δ is the ratio of the largest to the smallest-cost edge in G, and τ (n, e) is the query and update time of an (e c)-ANN data structure for some constant c > 1. We show that our results lead to faster matching algorithms for many geometric settings.
summary: Approximation results are known for general bipartite matching in metric spaces; in @cite_2 the authors show that for any @math , there is an algorithm that computes a @math -approximate matching, where @math in @math time. A variation on minimum-distance bottleneck matching, with the additional constraint that the matched edges cannot cross, was recently shown to be NP-hard to approximate within a factor of less than @math @cite_7 .