On The Rectangle Escape Problem

Authors: Sepehr Assadi, Ehsan Emamjomeh-Zadeh, Sadra Yazdanbod, Hamid Zarrabi-Zadeh
Journal: Theoretical Computer Science, 689:126–136, 2017.
Conference: The 25th Canadian Conference on Computational Geometry (CCCG'13).
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]
Journal version: [PDF]
BibTex: [DBLP]