{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreid7mp3md2retisd5df5w5fqpf4elkanxqt62mzplrkg4ceakbccki",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mgw2pwvty6x2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2603.11775v1",
  "publishedAt": "2026-03-13T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Joost van der Laan",
    "Frank Staals",
    "Lorenzo Theunissen"
  ],
  "textContent": "**Authors:** Joost van der Laan, Frank Staals, Lorenzo Theunissen\n\nWe present efficient data structures for approximate nearest neighbor searching and approximate 2-point shortest path queries in a two-dimensional polygonal domain $P$ with $n$ vertices. Our goal is to store a dynamic set of $m$ point sites $S$ in $P$ so that we can efficiently find a site $s \\in S$ closest to an arbitrary query point $q$. We will allow both insertions and deletions in the set of sites $S$. However, as even just computing the distance between an arbitrary pair of points $q,s \\in P$ requires a substantial amount of space, we allow for approximating the distances. Given a parameter $\\varepsilon > 0$, we build an $O(\\frac{n}{\\varepsilon}\\log n)$ space data structure that can compute a $1+\\varepsilon$-approximation of the distance between $q$ and $s$ in $O(\\frac{1}{\\varepsilon^2}\\log n)$ time. Building on this, we then obtain an $O(\\frac{n+m}{\\varepsilon}\\log n + \\frac{m}{\\varepsilon}\\log m)$ space data structure that allows us to report a site $s \\in S$ so that the distance between query point $q$ and $s$ is at most $(1+\\varepsilon)$-times the distance between $q$ and its true nearest neighbor in $O(\\frac{1}{\\varepsilon^2}\\log n + \\frac{1}{\\varepsilon}\\log n \\log m + \\frac{1}{\\varepsilon}\\log^2 m)$ time. Our data structure supports updates in $O(\\frac{1}{\\varepsilon^2}\\log n + \\frac{1}{\\varepsilon}\\log n \\log m + \\frac{1}{\\varepsilon}\\log^2 m)$ amortized time.",
  "title": "Approximate Dynamic Nearest Neighbor Searching in a Polygonal Domain"
}