cs.DS cs.CG
Pattern Matching in Doubling Spaces. We consider the problem of matching a metric space (X,d X) of size k with a subspace of a metric space (Y,d Y) of size n geq k , assuming that these two spaces have constant doubling dimension delta . More precisely, given an input parameter rho geq 1 , the rho distortion problem is to find a one to one mapping from X to Y that distorts distances by a factor at most rho . We first show by a reduction from k clique that, in doubling dimension log 2 3 , this problem is NP hard and W 1 hard. Then we provide a near linear time approximation algorithm for fixed k Given an approximation ratio 0 varepsilon leq 1 , and a positive instance of the rho distortion problem, our algorithm returns a solution to the (1 varepsilon) rho distortion problem in time ( rho varepsilon) O(1) n log n . We also show how to extend these results to the minimum distortion problem in doubling spaces We prove the same hardness results, and for fixed k , we give a (1 varepsilon) approximation algorithm running in time ( dist (X,Y) varepsilon) O(1) n 2 log n , where dist (X,Y) denotes the minimum distortion between X and Y .