2026-08-25T18:47:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27185 2026-08-25T13:18:17Z ddc:004 open_access

Computational Boundaries for Escaping Rectangles Agrawal, Akanksha Ashok, Pradeesha Bentert, Matthias Jana, Satyabrata Sahu, Abhishek Saurabh, Saket Singanporia, Kushal NP-hardness Sweep-line algorithm Fixed-parameter tractability Tight lower and upper bounds Ma and Wong [IEEE TCAD '12] introduced and studied the Rectangle Escape problem, motivated by bus escape routing in printed circuit board design. In this problem, we are given an axis-parallel rectangle R, a set 𝒮 of axis-parallel rectangles fully contained in R, and an integer d. The goal is to determine whether each rectangle in 𝒮 can be extended in one of the four axis-parallel directions (up, down, left, or right) to the boundary of R such that no point is covered by more than d extended rectangles. We revisit Rectangle Escape and resolve several open complexity questions. Ahmadinejad et al. [TCS '17] studied Rectangle Escape and its variants where rectangles are only allowed to be extended in a subset of directions - most notably, in two directions, a variant they termed Bidirectional REP. They showed that the problem is NP-complete when extensions are limited to two adjacent directions and d = 3, but left open the complexity of the case when d = 2. Additionally, the case for two opposite directions remained unresolved for any d ≥ 2. We resolve the first question by showing that Bidirectional REP is NP-complete even when extensions are restricted to two adjacent directions and d = 2. We also settle the complexity of Rectangle Escape with two opposite directions by proving that the problem is NP-complete when d is part of the input but solvable in 𝒪(n log n) time for any constant d. Finally, we consider the special case where all extended rectangles must be disjoint, that is, d = 1. We show an unconditional lower bound of Ω(n log n) with a matching upper bound of 𝒪(n log n) for all variants. This improves upon a sequence of algorithms for the setting with all four directions allowed and d = 1, starting with an 𝒪(n⁶)-time algorithm, later improved to 𝒪(n⁴), and then to O(n³). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Akanksha Agrawal and Pradeesha Ashok and Matthias Bentert and Satyabrata Jana and Abhishek Sahu and Saket Saurabh and Kushal Singanporia 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.49 urn:nbn:de:0030-drops-271858 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.49 eng https://creativecommons.org/licenses/by/4.0/legalcode