I'd recommend using a kd-tree or an R-tree. These structures automatically partition the data.
A kd-tree (k-dimensional tree) is a binary tree in which every node is a point. Every non-leaf node splits the space in half along one of the axes. Points on one side of the split form the left subtree, points on another side form the right subtree. A kd-tree has guaranteed space complexity O(n) and average search, insertion and deletion complexity of O(log n). The cost of building the tree is O(n log n) when using an advanced linear median-finding algorithm. The k-nearest-neighbors search boils down to moving down the tree, checking distances to the elements in final subtree and unwinding the recursion up the tree if more elements are needed. kd-trees are easy to implement in memory, but non-trivial to implement on disk. They may need to be rebuilt when changing data.
R-trees (rectangle trees) group nearby objects in minimum bounding rectangles, group the rectangles in larger rectangles, and so on. This means that they can store not only points, but also polygons. The complexity of search is between O(log n) and O(n), depending on the amount of overlap between rectangles. There are various optimization strategies and algorithms for splitting overflowing nodes and bulk-loading. While more complicated, R-trees have advantages over kd-trees. They are more disk-oriented, making them useful for real databases. Unlike non-bulk-loaded kd-trees, they are balanced, and therefore preferred for changing data.
In conclusion, if the data will change after building the tree or you want the data to be stored on disk, I'd use an R-tree, otherwise kd-tree.
