Building and balancing a k-d tree is not free, either. I suspect that the GP's approach is roughly the same in terms of theoretical complexity, but effectively

Building and balancing a k-d tree is not free, either. I suspect that the GP's approach is roughly the same in terms of theoretical complexity, but effectively trades memory for smaller constants and a chance to trip over edge cases like dense groups of points.