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
|a| denotes the size of the set of points)
However, I am wondering if there are even faster approaches to solve this problem.