Reductions Among High Dimensional Proximity Problems
Ashish Goel, Piotr Indyk, Kasturi Varadarajan · 2000
We present improved running times for a wide range of approximate high dimensional proximity problems. We obtain subquadratic running time for each of these problems. These improved running times are obtained by reduction to Nearest Neighbour queries. The problems we consider in this paper are Approximate Diameter, Approximate Furthest Neighbours, Approximate Discrete Center, Approximate Line Center, Approximate Metric Facility Location, Approximate Bottleneck Matching, and Approximate Minimum Weight Matching. University of Southern California. Email: [email protected] . y Stanford University. Email: [email protected] . z University of Iowa. Email: [email protected] . 0 Problem Ref Approx. Time Comments Diameter [10] p 3 O(dn) [12] 1 + ffl O(dn log n + n 2 ) [2] 1 + ffl ~ O(n 2\\GammaO(ffl 2 ) + dn) [18] 1 + ffl ~ O(n 1+1=(1+ffl=6) + dn) here 1 + ffl ~ O(n 1+1=(1+ffl) + dn) ~ O(n) (1 + ffl)-NNS queries here p 2 ~ O(dn) see Section 3 for some e...