Random hyperplane search trees in high dimensions

Luc Devroye, James King


Given a set S of nd points in general position in Rd, 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))) log2n and average element depth at most (1 + O(1/d)) log2n with high probability as n → ∞. Further, we show that these bounds are asymptotically optimal with respect to d.

Full Text:


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

ISSN: 1920-180X