The animation involves a group of nodes floating around inside a container. Each time the user moves the mouse, the node closest to the pointer is highlighted. The highlighted node connects to its closest neighbor nodes, which repeat the process to connect to their neighbors. This process recurs up to a certain depth.

A k-d tree may seem difficult to imagine. To visualize how the tree stores data, let's take the simplest case: one dimension. It turns out that a one-dimensional k-d tree is just a binary search tree. Each binary search tree contains a root node with two leaves. In a balanced BST, the root represents the median of the data; it splits the data into two equal halves. Down the tree, each node splits its subset of the data in half again.

Now imagine this in two dimensions. Instead of representing a single number, each node represents two: a point on the Cartesian plane. This point also represents a line down the center of the data set. (The line is determined based on the k-d tree algorithm and varies by implementation.) To split a set of points in two dimensions, you just have to figure out which side of the line each point falls on.

Take this up one more dimension and each node represents a three numbers: a point in a three-dimensional coordinate system. This point is used to determine a plane in three-dimensions. Each node in its subtree represents another point in three dimensions. If the tree is balanced, exactly half of the nodes are on one side of the root node's plane and half are on the other.

Now we've taken a one-dimensional tree (a BST) and abstracted it to two and three dimensions. A point became a line and then a plane. It's easy now to take these concepts up to four dimensions. And five. All we need for a tree in

As we know from Binary Search Tree implementations, sorting data into a tree speeds up search dramatically. Each step of search can discard half of the data by slicing it down the middle. Therefore, in a tree of

When the user's mouse position changes within the container, the algorithm searches the tree for the nodes closest to the mouse. Then, for each of these nodes, it searches for the next-closest nodes. These steps recur until the maximum depth for each frame. I've chosen a shallow depth for demonstration purposes.

Computation time could be reduced by pre-computing each node's neighbors. However, in my implementation, I chose to add a bit of life by giving each node a slight velocity in a random direction. As such, the list of neighbors could change on each frame and must be recomputed.

(mouse over this box)