### Random hyperplane search trees in high dimensions

#### Abstract

Given a set *S* of *n* ≥ *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* → ∞. Further, we show that these bounds are asymptotically optimal with respect to *d*.

#### Full Text:

PDFDOI: http://dx.doi.org/10.20382/jocg.v6i1a6

ISSN: 1920-180X