3
$\begingroup$

My background is not CS so sorry for using improper term. But basically I want to check if a point on XY plane is "too close" to any other points, and do so with every points. In another words, if I draw a circle with radius R at every points, would any circle cross other circles on the plane.

I want to code this in Python, if that matters.

$\endgroup$
  • $\begingroup$ Maybe this will help. $\endgroup$ – Gokul May 4 at 6:25
3
$\begingroup$

The problem you are solving has many well-known efficient algorithms.

The problem is to find closest pair of points in the plane.
If the closest pair have distance less than the safety distance, you already have a pair.
If not, no other pair can have a less distance, and hence all pairs are safe.

One efficient way to solve this problem is using divide and conquer. The algorithm is practical and easy to implement. It has run-time $O(n \log n)$ (check the notes at the end).

It might be an over-kill, but as efficient from the theoretical point of view, to build Delaunay-Triangulation over the set of points and compare each point to its neighbors in the triangulation, which is also achievable in $O(n \log n)$.

There are many libraries that offer a ready-to-use Delaunay-Triangulation (you can check CGAL-Boost library for C++), which makes it an easier way to implement that the previous method.

ps. Another very well-known approach, used in many different problems is line-sweep. There is also a line-sweep $O(n \log n)$ algorithm for Closest pair of points problem. (please check the link).

$\endgroup$
  • 1
    $\begingroup$ "The problem is to find the closest distance in the plane" - no, it's not. The problem is showing there is no distance below the minimum safe distance. $\endgroup$ – gnasher729 May 4 at 17:52
  • $\begingroup$ I know, the two lines following that line explain why both problems are equivalent in this context $\endgroup$ – narek Bojikian May 4 at 20:18
  • 1
    $\begingroup$ They are not, because if I take the first two points and they are close together, Op’s Question is answered. The problem you want to solve is generally much harder. $\endgroup$ – gnasher729 May 5 at 16:06
0
$\begingroup$

If you have many points, say a million, you want to do something that is faster than comparing each point to each other point.

There is a simple method that is far from perfect but will give you a significant advantage:

You start by sorting all the points by their x-value. The way you describe it, you want the distance between any two points to be at least 2R. So you iterate through the points, and for each point with x-coordinate X, you only examine the following points in the sorted array as long as their x-coordinate is at most X + 2R.

You know you have checked previous points in the sorted array earlier, so they don't need to be checked again. As a result, instead of comparing a point with all other points, you only compare it with points in the stripe X to X+2R. That should reduce the number of points to compare a lot.

$\endgroup$
0
$\begingroup$

You can use a spatial index, such as quadtree, kd-tree, R-tree, ... . Most implementations of spatial indexes provide a search method that returns all indexed points in a circle or rectangle. Before inserting any point P, you can simply query/search the index whether there is already any point in the rectangle/circle around P, where the rectangle/circle encompasses the safety distance. Of course, if you use a rectangle, you have to manually check whether the returned points really violate the safety distance.

These searches are usually in the order of $O(log (n))$, so checking all points requires something like $O(n * log(n))$.

$\endgroup$

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.