<p>It is known that a kd-tree can be constructed for <span class="math-container">$n$</span> points (<span class="math-container">$k$</span>-dimensional) in <span class="math-container">$O(n \log n)$</span> time and searching of any axis-aligned hyperrectangle can be done in time <span class="math-container">$O(n^{1-1/k} + out)$</span> time where <span class="math-container">$out$</span> is the number of points in the hyperrectangle. Is this optimal, i.e., is it known that there cannot be a data structure that can be built in <span class="math-container">$O(n \log n)$</span> time and allows orthogonal range search in <span class="math-container">$O(n^{1-1/k - \epsilon} + out)$</span> time for any constant <span class="math-container">$\epsilon &gt; 0$</span>?</p>

CC BY-SA 4.0
2023-07-30T06:29:27.710Z
I believe it can be done in $O(\log^k(n)+out)$
Command Master
CC BY-SA 4.0
2023-07-30T13:25:38.383Z
Yes, using range trees, but range trees cannot be constructed in $O(n \log n)$ time. My question is specifically for only $O(n \log n)$ time allowed.
karmanaut
CC BY-SA 4.0
2023-07-30T23:43:33.353Z
For $k=2$, this is definitely false. Range trees with fractional cascading can build the tree in $O(n \log n)$ and answer the query in $O(\log n)$
user3508551
<ds.algorithms><ds.data-structures><computational-geometry><high-dimensional-geometry>
kd-tree optimality for orthogonal range search
karmanaut
# kd-tree optimality for orthogonal range search

(Asked by: username_0 on 2023-07-30)

It is known that a kd-tree can be constructed for $n$ points ($k$-dimensional) in $O(n \log n)$ time and searching of any axis-aligned hyperrectangle can be done in time $O(n^{1-1/k} + out)$ time where $out$ is the number of points in the hyperrectangle. Is this optimal, i.e., is it known that there cannot be a data structure that can be built in $O(n \log n)$ time and allows orthogonal range search in $O(n^{1-1/k - \epsilon} + out)$ time for any constant $\epsilon > 0$?

**Tags:** ds.algorithms, ds.data-structures, computational-geometry, high-dimensional-geometry

> **Comments:**
> **username_1**: I believe it can be done in $O(\log^k(n)+out)$  
> **username_0**: Yes, using range trees, but range trees cannot be constructed in $O(n \log n)$ time. My question is specifically for only $O(n \log n)$ time allowed.  
> **username_2**: For $k=2$, this is definitely false. Range trees with fractional cascading can build the tree in $O(n \log n)$ and answer the query in $O(\log n)$  

---

## 0 answers

