# Parallel building time of a k-d tree on n points with n processors

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