5

In my contrived example, I have a rectangular grid of nodes, where each node is either empty, of Type 1 or of Type 2. All nodes are directed to the eight nodes around them (horizontal, vertical, diagonal). For each of the nodes of Type 1, I want to find the distance to the closest node of Type 2. For all points, their (x,y) positions on the grid are known.

The naïve approach I can think of is something like this (in pseudocode):

for p1 ∈ Type1Points
    min = ∞
    for p2 ∈ Type2Points
        possibility = max(abs(p1.x-p2.x), abs(p1.y-p2.y))
        if possibility < min
            min = possibility
    output min

This seems to run in O(|Type1Points|*|Type2Points|) (where |a| denotes the size of the set of points) However, I am wondering if there are even faster approaches to solve this problem.

  • 2
    How large is the grid? Certain approaches with bad Big-O might be acceptable with small enough inputs. – user22815 Mar 13 '17 at 18:08
  • 1
    You may get better performance if you sort Type2Points by either x or y and limit the inner loop to points within min. BTW to compute the correct distance in two-dimensional space you should be using the Pythagorean theorem. – John Wu Mar 13 '17 at 18:12
  • @Snowman The grid is at most 2000*2000. There are at most 10.000 points of Type 1, and at least 1 point of Type 2. (But on the other hand, the whole grid could be filled with them). – Qqwy Mar 13 '17 at 18:36
  • @JohnWu Yes, for many problems using the Euclidean Distance might be more appropriate, but in this case the problem works with the cardinal+ordinal directions. – Qqwy Mar 13 '17 at 18:39
  • Additional thought: if your approach would be to find the type 1 points first and then look around each for the nearest type 2, you could easily apply multi-threading. Set up a thread pool where each thread picks the next T1 from the list until you are done. – Martin Maat Mar 14 '17 at 7:02
5

An efficient algorithm is likely to be one making use of R-trees. The algorithm would be something like

type1RTree = new RTree()
for p1 in Type1Points
    type1RTree.insert(p1)
min = inf
for p2 in Type2Points
    nearest_p1 = type1RTree.nearest-neighbor(p2)
    possibility = distance(p2, nearest_p1)
    if possibility < min
        min = possibility
output min

Most every language should have a decent R-tree implementation somewhere; you can also see the linked wiki article for implementation sketches of insert and nearest-neighbor.

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.