The QuadTree data structure is useful for fast, neighborhood-restricted lookups. We use it to implement fast k-Nearest Neighbor and Rectangular range lookups in 2 dimenions. The primary target is high performance interactive graphics.
