  Given a set S of n \geq d points in general position in R^d, a random
hyperplane split is obtained by sampling d points uniformly at random without
replacement from S and splitting based on their affine hull. A random
hyperplane search tree is a binary space partition tree obtained by recursive
application of random hyperplane splits. We investigate the structural
distributions of such random trees with a particular focus on the growth with
d. A blessing of dimensionality arises--as d increases, random hyperplane
splits more closely resemble perfectly balanced splits; in turn, random
hyperplane search trees more closely resemble perfectly balanced binary search
trees.
  We prove that, for any fixed dimension d, a random hyperplane search tree
storing n points has height at most (1 + O(1/sqrt(d))) log_2 n and average
element depth at most (1 + O(1/d)) log_2 n with high probability as n
\rightarrow \infty. Further, we show that these bounds are asymptotically
optimal with respect to d.
