Journal:
Theoretical Computer Science, 689:126–136, 2017.
Abstract:
Motivated by a PCB routing application, we study the
following rectangle escape problem: Given a set S of n
rectangles inside a 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,
where 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
any factor better than 3/2. We then provide a randomized
algorithm that achieves an approximation factor
of 2 with high probability when the optimal solution
is sufficiently large, improving upon the current best
4-approximation algorithm available for the problem.
When the optimal density is one, we provide an exact
algorithm that finds an optimal solution in O(n^4) time,
improving upon the current best O(n^6)-time algorithm.
Conference version:
[PDF]