DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2026.49

Computational Boundaries for Escaping Rectangles

Authors: Akanksha Agrawal, Pradeesha Ashok, Matthias Bentert, Satyabrata Jana, Abhishek Sahu, Saket Saurabh, and Kushal Singanporia

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract

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

Cite as

Akanksha Agrawal, Akanksha Agrawal, Pradeesha Ashok, Pradeesha Ashok, Matthias Bentert, Matthias Bentert, Satyabrata Jana, Satyabrata Jana, Abhishek Sahu, Abhishek Sahu, Saket Saurabh, Saket Saurabh, Kushal Singanporia, and Kushal Singanporia. Computational Boundaries for Escaping Rectangles. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 49:1-49:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.ESA.2026.49,
  author =	{Agrawal, Akanksha and Ashok, Pradeesha and Bentert, Matthias and Jana, Satyabrata and Sahu, Abhishek and Saurabh, Saket and Singanporia, Kushal},
  title =	{{Computational Boundaries for Escaping Rectangles}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{49:1--49:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.49},
  URN =		{urn:nbn:de:0030-drops-271858},
  doi =		{10.4230/LIPIcs.ESA.2026.49},
  annote =	{Keywords: NP-hardness, Sweep-line algorithm, Fixed-parameter tractability, Tight lower and upper bounds}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2017.11

Exact Algorithms for Terrain Guarding

Authors: Pradeesha Ashok, Fedor V. Fomin, Sudeshna Kolay, Saket Saurabh, and Meirav Zehavi

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract

Given a 1.5-dimensional terrain T, also known as an x-monotone polygonal chain, the Terrain Guarding problem seeks a set of points of minimum size on T that guards all of the points on T. Here, we say that a point p guards a point q if no point of the line segment pq is strictly below T. The Terrain Guarding problem has been extensively studied for over 20 years. In 2005 it was already established that this problem admits a constant-factor approximation algorithm [SODA 2005]. However, only in 2010 King and Krohn [SODA 2010] finally showed that Terrain Guarding is NP-hard. In spite of the remarkable developments in approximation algorithms for Terrain Guarding, next to nothing is known about its parameterized complexity. In particular, the most intriguing open questions in this direction ask whether it admits a subexponential-time algorithm and whether it is fixed-parameter tractable. In this paper, we answer the first question affirmatively by developing an n^O(sqrt{k})-time algorithm for both Discrete Terrain Guarding and Continuous Terrain Guarding. We also make non-trivial progress with respect to the second question: we show that Discrete Orthogonal Terrain Guarding, a well-studied special case of Terrain Guarding, is fixed-parameter tractable.

Cite as

Pradeesha Ashok, Fedor V. Fomin, Sudeshna Kolay, Saket Saurabh, and Meirav Zehavi. Exact Algorithms for Terrain Guarding. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{ashok_et_al:LIPIcs.SoCG.2017.11,
  author =	{Ashok, Pradeesha and Fomin, Fedor V. and Kolay, Sudeshna and Saurabh, Saket and Zehavi, Meirav},
  title =	{{Exact Algorithms for Terrain Guarding}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{11:1--11:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.11},
  URN =		{urn:nbn:de:0030-drops-71975},
  doi =		{10.4230/LIPIcs.SoCG.2017.11},
  annote =	{Keywords: Terrain Guarding, Art Gallery, Exponential-Time Algorithms}
}

Search Results

Documents authored by Ashok, Pradeesha

Computational Boundaries for Escaping Rectangles

Abstract

Cite as

Exact Algorithms for Terrain Guarding

Abstract

Cite as

Thanks for your feedback!

Could not send message