Random hyperplane search trees in high dimensions

Details Random hyperplane search trees in high dimensions Random hyperplane search trees in high dimensions

2011-06-02

arxiv.org/abs/1106.0461v1

Computer Science

Computational Geometry

19 pages, 4 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Random hyperplane search trees in high dimensions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Random hyperplane search trees in high dimensions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Random hyperplane search trees in high dimensions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-495557