Discrete Fréchet Distance Oracles

Boris Aronov, Tsuri Farhana, Matthew J. Katz +1

It is unlikely that the discrete Fréchet distance between two curves of length $n$ can be computed in strictly subquadratic time. We thus consider the setting where one of the curv…