How to efficiently determine if a set of points contains two that are close?

Question

I need to determine if a set of points (each given by a tuple of floats, each of which is in [0, 1]) contains two that are within some threshold, say 0.01, of each other. I should also mention that in the version of the problem that I am interested in, these "points" are given by tuples of length ~30, that is they are points in [0, 1]^30. I can test if any two are within this threshold using something like: def is_near(p1, p2): return sqrt(sum((x1 - x2)**2 for x1, x2 in zip(p1, p2))) < 0.01 # Threshold. Using this I can just check every pair using something like: def contains_near(points): from itertools import combinations return any(is_near(p1, p2) for p1, p2 in combinations(points, r=2)) However this is quadratic in the length of the list, which is too slow for the long list of points that I have. > Is there an n log n way of solving this? I tried doing things like snapping these points to a grid so I could use a dictionary / hash map to store them: def contains_near_hash(points): seen = dict() for point in points: # The rescaling constant should be 1 / threshold. grid_point = tuple([round(x * 100, 0) for x in point]) if grid_point in seen: for other in seen[grid_point]: if is_near(point, other): return True seen[grid_point].append(point) else: seen[grid_point] = [point] return False However this doesn't work when points = [(0.1149999,), (0.1150001,)] As these round to two different grid points. I also tried a version in which the point was appended to all neighbouring grid points however as the examples that I want to do have ~30 coordinates, each grid point has 2^30 neighbours which makes this completely impractical.

Answer 1

First create the pythagorean function or macro that calculates the distance between two points.

Next create a data structure with the following field columns:

point_P1 : Point

point_P2 : Point

distance : float

Step 3, using nested for loop, calculate the distance between all possible pairs of points.

If you have N points, then there are N choose 2 pairs, which is n!/ (2! (n-2)!) =

n(n-1)/2 pairs

So if you have 10 points, there are 45 pairs, of which you must find the pythagorean distance of each.

Step 4: sort these data structures or linear search them for one within the threshold