Search Results

Documents authored by Xu, Xiaoyang

Document
DOI: 10.4230/LIPIcs.ESA.2026.69
Parameterized Approximation of Rectangle Stabbing

Authors: Huairui Chu, Ajaykrishnan E S, Daniel Lokshtanov, Anikait Mundhra, Thomas Schibler, Xiaoyang Xu, and Jie Xue

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

Abstract
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.
Cite as

Huairui Chu, Ajaykrishnan E S, Daniel Lokshtanov, Anikait Mundhra, Thomas Schibler, Xiaoyang Xu, and Jie Xue. Parameterized Approximation of Rectangle Stabbing. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 69:1-69:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chu_et_al:LIPIcs.ESA.2026.69,
  author =	{Chu, Huairui and E S, Ajaykrishnan and Lokshtanov, Daniel and Mundhra, Anikait and Schibler, Thomas and Xu, Xiaoyang and Xue, Jie},
  title =	{{Parameterized Approximation of Rectangle Stabbing}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{69:1--69:20},
  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.69},
  URN =		{urn:nbn:de:0030-drops-272056},
  doi =		{10.4230/LIPIcs.ESA.2026.69},
  annote =	{Keywords: rectangle stabbing, parameterized algorithms, approximation algorithms, computational geometry, parameterized approximation complexity, geometric hitting set, lower bounds}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact