Given a point set with $n$ points to build a k-d tree on. We have $n$ processors available. What is the time-optimal building time for the k-d tree?
A straight forward parallelization would be as follows: In each step $i$, we have to sort $i$ sets of $n^2/2^i$ points in the dimension with largest spread, which takes $\log(n^2)-i$ time for each of the $\log(n^2)$ levels of the tree, resulting in an upper bound for the total building time of $\Omega(\log^2(n))$.
However, this only holds for a straight forward parallelization. As a k-d tree can be used for sorting by placing all points along one dimension, by e.g. this paper, it therefore has a minimum build time of $\mathcal{O}(\log(n))$.
Can this gap be closed in either direction? That is: Can the k-d tree be built in $\Theta(\log(n))$ or $\Theta(\log^2(n))$?
