Discrete Fréchet Distance Oracles

Boris Aronov, Tsuri Farhana, Matthew J. Katz, Indu Ramesh

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    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 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 Θ(nα), for any α > 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échet distance between the segment and any (u, v)-path in G. The answer is exact, if t = 1, and approximate if t > 1.

    Original languageEnglish (US)
    Title of host publication40th International Symposium on Computational Geometry, SoCG 2024
    EditorsWolfgang Mulzer, Jeff M. Phillips
    PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
    ISBN (Electronic)9783959773164
    StatePublished - Jun 2024
    Event40th International Symposium on Computational Geometry, SoCG 2024 - Athens, Greece
    Duration: Jun 11 2024Jun 14 2024

    Publication series

    NameLeibniz International Proceedings in Informatics, LIPIcs
    ISSN (Print)1868-8969


    Conference40th International Symposium on Computational Geometry, SoCG 2024


    • discrete Fréchet distance
    • distance oracle
    • heavy-path decomposition
    • t-local graphs

    ASJC Scopus subject areas

    • Software


    Dive into the research topics of 'Discrete Fréchet Distance Oracles'. Together they form a unique fingerprint.

    Cite this