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$?

  • $\begingroup$ I believe it can be done in $O(\log^k(n)+out)$ $\endgroup$ Jul 30, 2023 at 6:29
  • $\begingroup$ 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. $\endgroup$
    – karmanaut
    Jul 30, 2023 at 13:25
  • 1
    $\begingroup$ 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)$ $\endgroup$ Jul 30, 2023 at 23:43


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.