Linear Time Maximum Clearance Computation on a Grid Graph? 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
All the sites are themselves grid points too, right? So I think it should work to compute the Delaunay triangulation of the sites in linear time using the word-model algorithm of Buchin and Mulzer (FOCS 2009), dualize to get the Voronoi diagram, and then fill out the grid neighbors within each Voronoi cell. The Delaunay part should be linear in the number of sites (its bottleneck is integer sorting, but for the magnitude of the integers in your problem sorting is easily done in time linear in the grid size).

To fill out the grid points within a single Voronoi cell, partition the cell along the lines connecting the cell's site to its neighbors and then find the grid points within each of the resulting quadrilaterals. That way it requires only a constant number of comparisons to determine whether any particular grid point belongs to the quadrilateral. Some quadrilaterals may be empty of grid cells but the total number of quadrilaterals formed in this way is linear so there isn't too much wasted work in the empty ones.