We revisit the problem of deciding whether a given curve resembles some part of a larger curve under a fixed Fréchet distance, achieving a running time of O(nm), for n and m being the number of segments in the two curves. This improves the long‐standing result of Alt and Godau by an O(log(nm)) factor. Our solution is based on constructing a simple data structure which we call free‐space map. Using this data structure, we obtain improved algorithms for several variants of the Fréchet distance problem, including the Fréchet distance between two closed curves, and the so‐called minimum/maximum walk problems. We also improve the map matching algorithm of Alt et al. for the particular case in which the map is a directed acyclic graph.
