The problem you are solving here is analogous to 2D Convolution:
--------------- --------------- -------XX------
-------X------- --------------- ------XXXX-----
------XXX------ -------XX------ -----XXXXXX----
-----XXXXX----- * ------XXX------ = ----XXXXXXX----
------XXX------ --------X------ -----XXXXXX----
-------X------- --------------- ------XXXX-----
--------------- --------------- --------X------
In your case where an element is only either covered or uncovered (versus containing a scalar or vector value), this reduces to the Dilation operation in morphology. There are many papers and code samples on efficient implementations of dilation - this one looks particularly applicable to your problem.