{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreietwr2btzx37fhw4qfwj6denpfzc6dtlvjcqw4rfvcgygflpq2alq",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mibqefzudj42"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2603.26585v1",
  "publishedAt": "2026-03-30T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Pankaj K. Agarwal",
    "Matthew J. Katz",
    "Micha Sharir"
  ],
  "textContent": "**Authors:** Pankaj K. Agarwal, Matthew J. Katz, Micha Sharir\n\nLet $K$ be a compact, centrally-symmetric, strictly-convex region in ${\\mathbb R}^3$, which is a semi-algebraic set of constant complexity, i.e. the unit ball of a corresponding metric, denoted as $\\|\\cdot\\|_K$. Let ${\\mathcal{K}}$ be a set of $n$ homothetic copies of $K$. This paper contains two main sets of results: (i) For a storage parameter $s\\in[n,n^3]$, ${\\mathcal{K}}$ can be preprocessed in $O^*(s)$ expected time into a data structure of size $O^*(s)$, so that for a query homothet $K_0$ of $K$, an intersection-detection query (determine whether $K_0$ intersects any member of ${\\mathcal{K}}$, and if so, report such a member) or a nearest-neighbor query (return the member of ${\\mathcal{K}}$ whose $\\|\\cdot\\|_K$-distance from $K_0$ is smallest) can be answered in $O^*(n/s^{1/3})$ time; all $k$ homothets of ${\\mathcal{K}}$ intersecting $K_0$ can be reported in additional $O(k)$ time. In addition, the data structure supports insertions/deletions in $O^*(s/n)$ amortized expected time per operation. Here the $O^*(\\cdot)$ notation hides factors of the form $n^\\varepsilon$, where $\\varepsilon>0$ is an arbitrarily small constant, and the constant of proportionality depends on $\\varepsilon$. (ii) Let $\\mathcal{G}(\\mathcal{K})$ denote the intersection graph of ${\\mathcal{K}}$. Using the above data structure, breadth-first or depth-first search on $\\mathcal{G}(\\mathcal{K})$ can be performed in $O^*(n^{3/2})$ expected time. Combining this result with the so-called shrink-and-bifurcate technique, the reverse-shortest-path problem in a suitably defined proximity graph of ${\\mathcal{K}}$ can be solved in $O^*(n^{62/39})$ expected time. Dijkstra's shortest-path algorithm, as well as Prim's MST algorithm, on a $\\|\\cdot\\|_K$-proximity graph on $n$ points in ${\\mathbb R}^3$, with edges weighted by $\\|\\cdot\\|_K$, can also be performed in $O^*(n^{3/2})$ time.",
  "title": "Dynamic Nearest-Neighbor Searching Under General Metrics in ${\\mathbb R}^3$ and Its Applications"
}