I have a uniform NxN grid with a non-empty subset of vertices marked as obstacles. My goal is to compute, for each non-obstacle vertex, the "maximum clearance" from the obstacle set. In other words, the radius of the largest circle center at the vertex not overlapping with any obstacle. Or the nearest "gas station" for each vertex. [sorry if there is some standard terminology I should have used]
I would like a linear-time algorithm to compute this. Can anyone help?
My gut feeling is that it is possible. I have searched but didn't get a straight answer, but I know the following:
(1) if the distance metric is Manhattan, this can be solved by a simple flooding.
(2) I know a little bit about Level Set, and it may help, but is there something simpler?
(3) I understand Fortune's elegant sweeping algorithm to calculate Voronoi diagram in O(n log n), where n is the number of points. For my particular application, since the wavefront never contains more than N vertices, the complexity is O(N log N). The O(log N) is due to updates to a binary tree. I hope this can be reduced from O(N log N) to O(N) because of the nature of my problem?
I am willing to do this in multiple passes in order to get linear time. For example, one pass each for N, E, S, W, which hopefully somewhat simplifies Fortune's algorithm. Also I am not interested in the Voronoi vertices but rather the distances of the grid vertices from the obstacles.
Is this a known, solved problem? If so, source code or (more detailed) pseudo code?
If not, so far what I have in mind is to do this in two passes (Eastbound sweep and Westbound sweep):
Consider the East-bound sweep, I update one column of N vertices at a time. There is a set of exactly N "back" vertices (each is assigned an X coordinate, or -infinity if they are out of scope (OOS)) such that a partition is defined by the bisecting lines between immediate non-OOS neighbors (similar to Fortune). In other words, each non-OOS vertex is given a range [ys, ye] which together partitions [0, N - 1]. I don't maintain a binary tree of non-OOS vertices. Instead, I always keep them in an array of size N.
When we move to the next column, the partition changes. The partition is recalculated, and if a vertex's range becomes negative (ys > ye), the vertex is marked as OOS accordingly. Hopefully, this can be done in O(N) time and hence the total runtime is O(NxN).
Am I going in the right direction? Actually by spelling it out it already helps a bit :D