{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiaqo6mny7jkju63tkasewzc3og7ijqlutvh6myx4u3imhclukr5da",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mhu7qpoynio2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2603.22500v1",
  "publishedAt": "2026-03-25T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Oliver Chubet",
    "Niyathi Kukkapalli",
    "Anvi Kudaraya",
    "Don Sheehy"
  ],
  "textContent": "**Authors:** Oliver Chubet, Niyathi Kukkapalli, Anvi Kudaraya, Don Sheehy\n\nGiven a metric space, a standard metric range search, given a query $(q,r)$, finds all points within distance $r$ of the point $q$. Suppose now we have two different metrics $d_1$ and $d_2$. A product range query $(q, r_1, r_2)$ is a point $q$ and two radii $r_1$ and $r_2$. The output is all points within distance $r_1$ of $q$ with respect to $d_1$ and all points within $r_2$ of $q$ with respect to $d_2$. In other words, it is the intersection of two searches. We present two data structures for approximate product range search in doubling metrics. Both data structures use a net-tree variant, the greedy tree. The greedy tree is a data structure that can efficiently answer approximate range searches in doubling metrics. The first data structure is a generalization of the range tree from computational geometry using greedy trees rather than binary trees. The second data structure is a single greedy tree constructed on the product induced by the two metrics.",
  "title": "Product Range Search Problem"
}