2026-08-25T18:47:27Z https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:27205 2026-08-25T13:18:17Z ddc:004 open_access
Parameterized Approximation of Rectangle Stabbing Chu, Huairui E S, Ajaykrishnan Lokshtanov, Daniel Mundhra, Anikait Schibler, Thomas Xu, Xiaoyang Xue, Jie rectangle stabbing parameterized algorithms approximation algorithms computational geometry parameterized approximation complexity geometric hitting set lower bounds In the Rectangle Stabbing problem, input is a set R of axis-parallel rectangles and a set L of axis-parallel lines in the plane. The task is to find a minimum size set L^* βŠ† L such that for every rectangle R ∈ R there is a line 𝓁 ∈ L^* such that 𝓁 intersects R. Gaur et al. [Journal of Algorithms, 2002] gave a polynomial time 2-approximation algorithm, while Dom et al. [WALCOM 2009] and Giannopoulos et al. [EuroCG 2009] independently showed that, assuming FPT β‰  W[1], there is no algorithm with running time f(k)(|L||R|)^O(1) that determines whether there exists an optimal solution with at most k lines. We give the first parameterized approximation algorithm for the problem with a ratio better than 2. In particular we give an algorithm that given R, L, and an integer k runs in time k^O(k)(|L||R|)^O(1) and either correctly concludes that there does not exist a solution with at most k lines, or produces a solution with at most 7k/4 lines. We complement our algorithm by showing that unless FPT = W[1], the Rectangle Stabbing problem does not admit a (5/4-Ξ΅)-approximation algorithm running in f(k)(|L||R|)^O(1) time for any function f and Ξ΅ > 0. Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik Huairui Chu and Ajaykrishnan E S and Daniel Lokshtanov and Anikait Mundhra and Thomas Schibler and Xiaoyang Xu and Jie Xue 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.69 urn:nbn:de:0030-drops-272056 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.69 eng https://creativecommons.org/licenses/by/4.0/legalcode