  It is unlikely that the discrete Fr\'echet distance between two curves of
length $n$ can be computed in strictly subquadratic time. We thus consider the
setting where one of the curves, $P$, is known in advance. In particular, we
wish to construct data structures (distance oracles) of near-linear size that
support efficient distance queries with respect to $P$ in sublinear time. Since
there is evidence that this is impossible for query curves of length
$\Theta(n^\alpha)$, for any $\alpha > 0$, we focus on query curves of (small)
constant length, for which we are able to devise distance oracles with the
desired bounds.
  We extend our tools to handle subcurves of the given curve, and even
arbitrary vertex-to-vertex subcurves of a given geometric tree. That is, we
construct an oracle that can quickly compute the distance between a short
polygonal path (the query) and a path in the preprocessed tree between two
query-specified vertices. Moreover, we define a new family of geometric graphs,
$t$-local graphs (which strictly contains the family of geometric spanners with
constant stretch), for which a similar oracle exists: we can preprocess a graph
$G$ in the family, so that, given a query segment and a pair $u,v$ of vertices
in $G$, one can quickly compute the smallest discrete Fr\'echet distance
between the segment and any $(u,v)$-path in $G$. The answer is exact, if $t=1$,
and approximate if $t>1$.
