On the rectangle escape problem

Amir Mahdi Ahmadinejad, Sepehr Assadi, Ehsan Emamjomeh-Zadeh, Sadra Yazdanbod, Hamid Zarrabi-Zadeh

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)126-136
Number of pages11
JournalTheoretical Computer Science
Volume689
DOIs
StatePublished - Aug 15 2017
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Approximation algorithms
  • Inapproximability
  • NP-completeness
  • Randomized rounding
  • Rectangle escape

Fingerprint

Dive into the research topics of 'On the rectangle escape problem'. Together they form a unique fingerprint.

Cite this