{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiceo3cj2ocphzb2hhkm2gwjozzx53ccsnxv2fuwiy2jyzfaug6nma",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mekn5ajtnwh2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2602.09551v1",
  "publishedAt": "2026-02-11T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Lotte Blank"
  ],
  "textContent": "**Authors:** Lotte Blank\n\nGiven two polygonal curves $P$ and $Q$ defined by $n$ and $m$ vertices with $m\\leq n$, we show that the discrete Fréchet distance in 1D cannot be approximated within a factor of $2-\\varepsilon$ in $\\mathcal{O}((nm)^{1-δ})$ time for any $\\varepsilon, δ>0$ unless OVH fails. Using a similar construction, we extend this bound for curves in 2D under the continuous or discrete Fréchet distance and increase the approximation factor to $1+\\sqrt{2}-\\varepsilon$ (resp. $3-\\varepsilon$) if the curves lie in the Euclidean space (resp. in the $L_\\infty$-space). This strengthens the lower bound by Buchin, Ophelders, and Speckmann to the case where $m=n^α$ for $α\\in(0,1)$ and increases the approximation factor of $1.001$ by Bringmann. For the discrete Fréchet distance in 1D, we provide an approximation algorithm with optimal approximation factor and almost optimal running time. Further, for curves in any dimension embedded in any $L_p$ space, we present a $(3+\\varepsilon)$-approximation algorithm for the continuous and discrete Fréchet distance using $\\mathcal{O}((n+m^2)\\log n)$ time, which almost matches the approximation factor of the lower bound for the $L_\\infty$ metric.",
  "title": "Fréchet Distance in the Imbalanced Case"
}