kD Trees

Nice features:



A tree. Each node an axis parallel split, with points in leaves. 


For a Kd tree storing the two dimensional location of a set of points:

Top Down:

It is expensive to find the meadian for each node; better to create a list of sorted points for each dimension. Then it is pretty easy to find the median quickly.

This procedure obviously generalizes to any dimension of input.


Finding the set of points within a window: if a node is completely contained in a region, then all of its children also are.
  This structure is useful for arbitrary objects; let each region in the graph be a bounding box for an object.

Find Nearest Neighbor to an object, O:

n-body problem

How can we efficiently simulate the movements of a collection of objects moving under mutual gravational attraction?


For each object, sum the force due to every other object. Uses O( n2 ) time.

Multipole Expansion:

Compute from the bottom up; that is, for each subdivision of space, figure out its total effect on the rest of space. Pass this quantity on to the parent of the subdivision. We are doing a calcultion on each node in the tree twice. O( n ) nodes, so this is algorithm uses O( n ) time.
What happens to the data structure when points move around?

Color Reduction:

What is an intelligent way to take a pick 256 colors to represent a full color image?


Median Cut Algorithm:

Build a tree with the set of colors used:  

[Start] [Back] [Next] 
Douglas De Couto

Joshua Napoli

Last modified: Tue Mar 17 09:49:02 1998