There has been a lot of work in this area. There is no best algorithm, it depends upon the problem that you are trying to solve. However, I think that r-trees have advantages over k-d trees for this 2d case. Alternatively, there are Quadtrees which have different trade-offs to r-trees. A very different approach is to use space-filling curves to reduce the 2d problem to a 1d problem; this approach is normally called geohashing. If you search on these terms then you can rapidly find resources and scientific papers to help you understand the algorithms.