2026-08-25T17:34:07Z https://drops.dagstuhl.de/oai

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

Covering Points with Rectangular Boundaries Kundu, Madhumita Lokshtanov, Daniel Nandi, Soumi Saurabh, Saket Singanporia, Kushal Geometric Covering Axis-parallel Rectangles W[1] and NP Hardness Fixed Parameter Tractability CSP 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Madhumita Kundu and Daniel Lokshtanov and Soumi Nandi 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.153 urn:nbn:de:0030-drops-272897 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.153 eng https://creativecommons.org/licenses/by/4.0/legalcode