2026/07/09 by Madhumita Kundu, Daniel Lokshtanov, Soumi Nandi +2
#cs.CG
Geometric covering problems ask for a small family of geometric objects whose union covers a given point set. We study the more restrictive boundary covering variant, where every point must lie on the boundary of a chosen object. Motivated by the framework of Langerman and Morin [Discret. Comput. Geom., 2005] for hyperspheres, we initiate the study of boundary covering by axis-parallel rectangles. We first consider the discrete setting, where rectangles must be selected from a given family. We define \bcdaprfull (\bcdaprshort): given a point set \(P⊆ℝ2\), a family \(R\) of axis-parallel rectangles, and an integer \(k\), decide whether \(P\) can be covered by the boundaries of at most \(k\) rectangles from \(R\). We prove that \bcdaprshort is \(W[1]\)-hard parameterized by \(k\). We then study the continuous variant, \prbcfull (\prbcshort), where rectangles may be placed freely. Given \(P⊆ℝ2\) and \(k\), the goal is to 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 \prbcshort is fixed-parameter tractable, with running time \(2\cO(klog k)⋅ n\cO(1)\), where \(n=|P|\). Our algorithm relies on a structural analysis of how \(k\) rectangles interact with the point set, reducing \prbcshort to at most \(2\cO(klog k)\) instances of \ddmtcsp, each solvable in polynomial time. On the hardness side, we prove NP-completeness for boundary covering by axis-aligned \(L\)-shapes and use this reduction to establish NP-completeness of \prbcshort.