Algorithm to synthesize a set of 2D points

Question

I have a set of 2D points/coordinates and I need that a certain minimum distance is respected between all pair of points. Also, each point is associated with some information that I would like to maintain, maybe merging that information with other information contained in other points.

The thing is that I have to create a new set where that minimum distance is respected between all pair of points and the least Information has been lost.

I can't think of an algorithm or method that solves this problem in any temporal cost.

Any help would be appreciated.

Answer 1

Naive solution -- not fast (O(n³)) but may get you started:

1. Find the minimum distance between any two points, i.e. the pair of points that globally have the minimal distance (O(n²))
2. If the distance is larger than the required minimum, you are done
3. Merge the two points and start at 1.

This merges the points that are most close together one by one use the brute force algorithm until the minimum distance is reached.

P.S.: As @Yyes Dauous mentioned in the comments, the closes pair can be found in O(n log n), as described e.g. in the corresponding Wikipedia article (which includes some discussion of dynamic aspects which may be useful here): https://en.wikipedia.org/wiki/Closest_pair_of_points_problem