On the d-Runaway Rectangle Escape Problem

Rectangle Escape comes out of routing buses on circuit boards: extend each rectangle inside a region to one of the four sides, keeping overlaps at any point low. I flip the objective. With overlap (density) capped at d, extend as many rectangles as possible, a problem that is polynomial for d = 1 and NP-hard for every d ≥ 2. I give a 4(1 + 1/(d−1))-approximation for disjoint rectangles, a 4d-approximation in general, an FPT algorithm (in the number of extended rectangles) for inputs of density below d, and hardness results, including NP-hardness for unit squares on a grid with d = 2.