Fr\\'echet distance: Given a set of $n$ polygonal curves with $m$ vertices, a

radius $\\delta > 0$, and a parameter $k \\leq m$, we want to preprocess the

curves into a data structure that, given a query curve $q$ with $k$ vertices,

either returns an input curve with Fr\\'echet distance at most $c\\cdot \\delta$

to $q$, or returns that there exists no input curve with Fr\\'echet distance at

most $\\delta$ to $q$. We focus on the case where the input and the queries are

one-dimensional polygonal curves -- also called time series -- and we give a

comprehensive analysis for this case. We obtain new upper bounds that provide

different tradeoffs between approximation factor, preprocessing time, and query

time.

Our data structures improve upon the state of the art in several ways. We

show that for any $0 < \\varepsilon \\leq 1$ an approximation factor of

$(1+\\varepsilon)$ can be achieved within the same asymptotic time bounds as the

previously best result for $(2+\\varepsilon)$. Moreover, we show that an

approximation factor of $(2+\\varepsilon)$ can be obtained by using

preprocessing time and space $O(nm)$, which is linear in the input size, and

query time in $O(\\frac{1}{\\varepsilon})^{k+2}$, where the previously best

result used preprocessing time in $n \\cdot O(\\frac{m}{\\varepsilon k})^k$ and

query time in $O(1)^k$. We complement our upper bounds with matching

conditional lower bounds based on the Orthogonal Vectors Hypothesis.

Interestingly, some of our lower bounds already hold for any super-constant

value of $k$. This is achieved by proving hardness of a one-sided sparse

version of the Orthogonal Vectors problem as an intermediate problem, which we

believe to be of independent interest.

},\n}\n"