On the rectangle escape problem

Motivated by the bus escape routing problem in printed circuit boards, we study the following rectangle escape problem: given a set S of n axis-aligned rectangles inside an axis-aligned rectangular region R, extend each rectangle in S toward one of the four borders of R so that the maximum density over the region R is minimized. The density of each point p∈R is defined as the number of extended rectangles containing p. We show that the problem is hard to approximate to within a factor better than 3/2 in general. When the optimal density is sufficiently large, we provide a randomized algorithm that achieves an approximation factor of 1+ε with high probability improving over the current best 4-approximation algorithm available for the problem. When the optimal density is one, we develop an exact algorithm that finds an optimal solution efficiently. We also provide approximation algorithms and inapproximability results for a restricted version of the problem where rectangles are allowed to escape toward only a subset of directions.