0

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.

5
  • Your question is not clear. Can you demonstrate an example and what have you tried?
    – barak1412
    Sep 20, 2015 at 18:35
  • @barak1412 I have edited the description, It's clearer now?
    – manelmc
    Sep 20, 2015 at 19:02
  • Maybe clustering the 2D points is what you are looking for. (en.wikipedia.org/wiki/Cluster_analysis)
    – barak1412
    Sep 20, 2015 at 19:12
  • Is there any issue with simply up-scaling the point set rather than trying to merge points? IE: Find the current min-distance, then multiply all the points by (desired min-distance) / (current min-distance) = scale factor. So if scale factor = 5, then (1,-9) becomes (5,-45).
    – Nuclearman
    Sep 21, 2015 at 1:48
  • Yes @Nuclearman, This problem is related with hydrometeorological analysis, so the coordinates and It's data are very important for a correct study. Scaling the set is not an option.
    – manelmc
    Sep 21, 2015 at 13:52

1 Answer 1

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

3
  • Thanks Stefan, It's a start. Let's see how it responds.
    – manelmc
    Sep 20, 2015 at 19:08
  • 1
    The closest point pair problem is solved in time O(N Log(N)). Merging the points turns it in a dynamic instance of the problem. I wouldn't be surprised that the next queries can be performed in time O(Log(N)) or so, leading to a much better complexity than O(N³).
    – user1196549
    Sep 21, 2015 at 15:55
  • 1
    A k-d tree is an option here. O(N log N) to build. O(log N) to find nearest neighbor O(log N) to remove a point. Use a priority queue to determine the next two closest points.
    – Nuclearman
    Sep 21, 2015 at 20:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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