KdTree

A data structure well suited for DynamicClustering. Read more about it [here]. There's many variations and nice applets to play with [here].

David Alves uses a KDTree in Phoenix 0.9XXDC, and Simonton uses one in DCResearch. With them the bots achieve very fast execution times even at hundreds of thousands of data points (such as when running a 500 round TargetingChallenge). Both of these bots use a [Bucket PR K-d Tree]. Simonton has made his implementation available here.