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 $δ$. More precisely, given an input parameter $ρ\geq 1$, the $ρ$-distortion problem is to find a one-to-one mapping from $X$ to $Y$ that distorts distances by a factor at most $ρ$. 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 $ρ$-distortion problem, our algorithm returns a solution to the $(1+\varepsilon)ρ$-distortion problem in time $(ρ/\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$.