{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiebmryuin4rtkj3hmgcn33iogzje3c2gommehnop2soxe5jvuvsti",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mkkzqdp75py2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.24135v1",
  "publishedAt": "2026-04-28T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Jacobus Conradi",
    "Ivor van der Hoog",
    "Frederikke Uldahl",
    "Eva Rotenberg"
  ],
  "textContent": "**Authors:** Jacobus Conradi, Ivor van der Hoog, Frederikke Uldahl, Eva Rotenberg\n\nThe Fréchet distance is a popular distance measure between trajectories or curves in space, or between walks in graphs. We study computing the Fréchet distance between walks in the $d$-dimensional grid graphs, i.e. $\\mathbb{Z}^d$ where points share an edge if they differ by one in one coordinate. We give an algorithm, that for two simple paths on $n$ vertices, $(1+\\varepsilon)$-approximates the Fréchet distance in time $\\widetilde{O}((\\frac{n}{\\varepsilon})^{2-2/d} +n)$. We complement this by a near-matching fine-grained lower bound: for constant dimensions $d \\geq 3$, there is no $O((\\varepsilon^{2/d}(\\frac{n}{\\varepsilon})^{2-2/d})^{1-δ})$ algorithm for any $δ>0$ unless the Orthogonal Vector Hypothesis fails. Thus, our results are tight up to a factor $\\varepsilon^{2/d}$ and $\\log(n)$-factors. We extend our results to imbalanced lower and upper bounds, where the curves have $n$ and $m$ vertices respectively, and also obtain near-tight bounds. Driemel, Har-Peled and Wenk [DCG'12] studied \\emph{realistic assumptions} for curves to speed up Fréchet distance computation. One of these assumptions is $λ$-low density and they can compute a $(1+\\varepsilon)$-approximation between $λ$-low dense curves in time $\\widetilde{O}( \\varepsilon^{-2} λ^2 n^{2(1-1/d)})$. By adapting our lower bound, we show that their algorithm has a tight dependency on $n$ and a tight dependency on $\\varepsilon$ as $d$ goes to infinity. A gap remains in terms of $λ$.",
  "title": "Near-tight Bounds for Computing the Fréchet Distance in d-Dimensional Grid Graphs and the Implications for λ-low Dense Curves"
}