I just started to read your problem, and I will continue to work on it, but I wanted to point something out.

I believe the non-Helicopter Hospitals add ellipse shapes to the 2d grid of coverage. The definition of an ellipse is that the sum of the distances from each point on it to two fixed foci is constant. One foci would be the helicopter-hospital, the other foci would be the non-heli-hospital. The distance would be 2X.

I don't have time to do anything else tonight, but this is a fun problem.