Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2603.22500 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912979943948288 |
|---|---|
| author | Chubet, Oliver Kukkapalli, Niyathi Kudaraya, Anvi Sheehy, Don |
| author_facet | Chubet, Oliver Kukkapalli, Niyathi Kudaraya, Anvi Sheehy, Don |
| contents | Given 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_22500 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Product Range Search Problem Chubet, Oliver Kukkapalli, Niyathi Kudaraya, Anvi Sheehy, Don Computational Geometry Given 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 |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2603.22500 |