0
$\begingroup$

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).

$\endgroup$
7
  • $\begingroup$ (You can interleave (fixed point?) coordinate bits: In, say, ascending order of coordinates, points close in position are close in Euclidean space.) $\endgroup$
    – greybeard
    Jul 18 at 16:47
  • 1
  • $\begingroup$ We don't normally use software suggestions here, but for nearest-neighbour search in C++, I can recommend nanoflann. $\endgroup$
    – Pseudonym
    Jul 19 at 6:01
  • 2
    $\begingroup$ Do you need one or all pairs within the threshold, or the closest two points? $\endgroup$
    – gnasher729
    Jul 19 at 7:03
  • 1
    $\begingroup$ "Two or more points": do you need to know all close pairs, or just check if there is one ? This makes a big difference. $\endgroup$ Jul 19 at 14:56

1 Answer 1

0
$\begingroup$

I've had to do something along these lines. My solution: Pick one of the dimensions and divide it into 'buckets' of width equal to the threshold (only finitely many buckets are required for finitely many points). Then place each point into its bucket; when doing so, check for proximity to another point against all points already in the same bucket plus the (at most) two immediately adjacent buckets. Because of the chosen bucket width, no point in any other bucket can be too close. If the points are reasonably scattered in two dimensions, there should need to be approximately O(N) comparisons, I estimate. Of course, it is possible for some point sets to be badly distributed (e.g all in one bucket), so you may need to do some preliminary calculation on the point set to pick which dimension is better to divide.

$\endgroup$
1
  • $\begingroup$ Assuming M buckets and a uniform distribution (a favorable case), you will need M.(N/M)²=N²/M comparisons. The idea can be extended to that of a grid with M² buckets, leading to N²/M² comparisons. $\endgroup$ Jul 19 at 15:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.