Partial recalculation of visibility on a 2D uniform grid

Question

Problem
Imagine that we have a 2D uniform grid of dimensions N x N. For this grid we have also pre-computed a visibility look-up table, e.g. with DDA, which answers the boolean query is cell X visible from cell Y?

The look-up table is a complete graph K_N of the cells V in the grid, with each edge E being a binary value denoting the visibility between its vertices.

Question
If any given cell has its visibility modified, is it possible to extract the subset E_delta of edges which must have their visibility recomputed due to the change, so as to avoid a full-on recomputation for the entire grid? (Which is N(N-1) / 2 or N² depending on the implementation)

Answer 1

Perhaps you should look at "The Visibility Skeleton: A Powerful And Efficient Multi-Purpose Global Visibility Tool," Durand et al., a 1997 paper that Google Scholar shows has been cited 148 times since. The question you pose has been heavily studied! One of the key search phrases is walkthrough.

Answer 2

If it is not possible to solve this in closed form, then maintaining a separate mapping of each cell and every cell pair which's line intersects said cell might also be an option. This obviously consumes more memory, but the data is static.

The increased memory requirement could be reduced by introducing a hierarchy, subdividing the grid into smaller parts, and by doing so the above mapping can be reused for each sub-grid. This would come at a cost in terms of increased computation relative to the number of subdivisions; also requiring a resumable ray-casting algorithm.