Yes, but the O(N) is generally only for pathological inputs.

Geo data is generally nicely distributed. R-tree (or similar) is the correct solution here.