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³).

Geometric covering problems typically ask for a small family of geometric objects whose union contains all input points. In this paper we study a more rigid variant, boundary covering, where every point must lie on the boundary of at least one chosen object. Motivated by the framework of Langerman and Morin [Discret. Comput. Geom., 2005] for boundary covering by hyperspheres, we initiate a systematic study of boundary covering by axis-parallel rectangles in the plane. We first consider the discrete setting, where the rectangles must be chosen from a given family. We define Boundary Covering with Discrete Axis-Parallel Rectangles (BCDAPR) as follows: given a point set P ⊆ ℝ², a collection ℛ of axis-parallel rectangles, and an integer k, decide whether P can be covered by the boundaries of at most k rectangles from ℛ. We prove that this discrete boundary-covering problem is W[1]-hard when parameterized by k. This motivates the continuous variant, where we are allowed to place rectangles freely. We define Boundary Covering with Continuous Axis-Parallel Rectangles (BCCAPR) as follows: given a point set P ⊆ ℝ² and an integer k, decide whether P can be covered by the boundaries of at most k axis-parallel rectangles. In contrast to the discrete case, we show that BCCAPR is fixed-parameter tractable parameterized by k, with running time 2^𝒪(k log k) ⋅ n^𝒪(1), where n = |P|. Our results does a fine-grained structural analysis of how k rectangles can interact with the point set. On the hardness side, we show that moving from lines to slightly richer shapes already incurs intractability: we prove NP-completeness for boundary covering by axis-aligned L-shapes, and then lift it to NP-completeness of BCCAPR. For the algorithm we reduce BCCAPR to at most 2^𝒪(k log k) instances of Distinct Domain Monotone ,$-CSP, each solvable in polynomial time.