Jamie King, School of Computer Science, McGill University
A random hyperplane search tree is a binary search tree structure for storing d-dimensional Euclidean point sets; I define their construction below. After giving an overview of random binary search trees and geometric split trees, I will discuss techniques used to analyze the height and depth of such random trees, then apply these techniques to random hyperplane search trees.
A random hyperplane search tree is constructed as follows. From our input set S of n points in general position, d are chosen uniformly at random to be stored in the root. These d points define a hyperplane that partitions the remaining n-d points into two disjoint sets S_1 and S_2. The left and right subtrees of the root are defined recursively as random hyperplane search trees constructed from S_1 and S_2 respectively. A set of fewer than d points is stored in a single external node.