# What is the fastest algorithm to find what point of Type 1 is closest for each point of Type 2 on a rectangular grid?

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.

• How large is the grid? Certain approaches with bad Big-O might be acceptable with small enough inputs.
– user22815
Mar 13, 2017 at 18:08
• 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. Mar 13, 2017 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, 2017 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, 2017 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. Mar 14, 2017 at 7:02

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`.