I have a vector of 2D Euclidean coordinates, and I need to find out if two or more points are within a distance threshold.
The naive approach is to compare each point with every other point, but I am not interested in O(n2) solutions. There are no other information or data that can be used to restrict the search space.
What is a good algorithm that has a runtime complexity of O(nlog(n)) or faster? I am working with C++, and I am looking into Boost's r-tree (not sure it is appropriate).