Pith. sign in

REVIEW 3 major objections 5 minor 25 references

Boundary covering of points by freely placed axis-parallel rectangles is fixed-parameter tractable when parameterized by the number of rectangles, even though the problem is NP-complete.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Covering points by boundaries of axis-parallel rectangles is NP-complete in the free-placement setting, W[1]-hard when rectangles are preset, and fixed-parameter tractable in the solution size k.

T0 review reviewed 2026-08-02 challenge →

load-bearing objection Interesting boundary-covering paper with a promising FPT/NP-hardness split, but the W[1]-hardness gadget has an off-by-one coverage bug and the claimed 2^{O(k log k)} running time does not follow from the proof as written. the 3 major comments →

arxiv 2607.08183 v2 pith:H2EDXKTK submitted 2026-07-09 cs.CG

Covering Points with Rectangular Boundaries

Madhumita Kundu , Daniel Lokshtanov , Soumi Nandi , Saket Saurabh , Kushal Singanporia This is my paper
classification cs.CG
keywords boundary coveringaxis-parallel rectanglesfixed-parameter tractabilityW[1]-hardnessNP-completenessDistinct Domain Monotone 2-CSPL-shape covergeometric covering
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper studies boundary covering: given a set of points in the plane, cover every point with the boundary (not the interior) of at most k axis-parallel rectangles. It proves that the discrete variant, where rectangles must be chosen from a given family, is W[1]-hard, so no algorithm of the form f(k) n^{O(1)} is expected under standard complexity assumptions. For the continuous variant, where rectangles may be placed anywhere, it proves NP-completeness but then gives a fixed-parameter algorithm with running time 2^{O(k log k)} n^{O(1)}. The algorithm guesses a small structural skeleton of the rectangle–point interaction, then reduces the remaining geometry to a polynomial-time-solvable constraint satisfaction problem. This matters because it draws a clean complexity line: the problem is as hard as any NP problem in general, yet becomes quickly solvable when the allowed number of rectangles is small.

Core claim

The central claim is that continuous axis-parallel rectangle boundary covering is fixed-parameter tractable parameterized by the number k of rectangles. The proof works by discretizing coordinates to grid lines, computing a set of at most 4k lines that together contain all input points, guessing a skeleton that specifies which rectangle side lies on which of these lines (or is unaligned), and then encoding the remaining feasibility as a Distinct Domain Monotone 2-CSP, a class with a polynomial-time algorithm. The paper also establishes NP-completeness of the continuous problem through an intermediate hardness proof for axis-aligned L-shapes, and W[1]-hardness of the discrete version.

What carries the argument

The core mechanism is the reduction to Distinct Domain Monotone 2-CSP: a constraint satisfaction problem where each variable has its own finite numeric domain and every constraint compares a variable to a monotone function of another variable (e.g., x ≤ f(y)). To make the reduction, the algorithm guesses a 'skeleton' — a mapping of each of the 4k rectangle sides to one of the at most 4k distinguished lines (or to a free/unassociated value) — then guesses the left-to-right order of endpoints on each line, counts how many exceptional points fall into each gap between balanced-parentheses blocks of that order, and assigns each exceptional point to a covering vertical or horizontal side. These g

Load-bearing premise

The FPT algorithm depends on the polynomial-time solver for Distinct Domain Monotone 2-CSP applying to the instances it builds, but the reduction in Section 6.10 generates constraints such as A_h(coord_h(e_first)) = GapFn(1) where a monotone counting function appears on the left-hand side, a form the paper's CSP definition does not allow.

What would settle it

Take a small Yes-instance (for example, four points forming a unit square with k=1), run the Section 6 reduction, and inspect the generated CSP: if any constraint has the form f(z_i) = z_j or f(z_i) ≤ z_j with a non-identity monotone function on the left, the instance is not a valid Distinct Domain Monotone 2-CSP as defined, and the paper's appeal to the polynomial-time algorithm is incomplete without additional argument.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • A Yes-instance with n points and k rectangles can be solved in time 2^{O(k log k)} n^{O(1)}, making the problem practical when k is small, up to roughly log n / log log n.
  • The discrete variant BCDAPR is W[1]-hard, so no fixed-parameter algorithm exists for it under the standard FPT ≠ W[1] assumption.
  • The continuous problem is NP-complete, so no polynomial-time algorithm for arbitrary k is expected; the FPT result shows the hardness is concentrated in the dependence on k.
  • Boundary covering by axis-aligned L-shapes is NP-complete, and the reduction from L-shapes to rectangles shows that fairly simple geometric families already produce hard boundary-covering problems.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The skeleton-and-CSP approach is likely reusable for other axis-parallel boundary-covering families, such as squares or rectangles with a fixed aspect ratio, because the core steps (grid discretization, few covering lines, endpoint orderings) do not rely on rectangles having arbitrary side lengths.
  • The NP-completeness of L-shape cover hints that boundary covering is sensitive to the shape family: covering by lines is polynomial-time solvable, while covering by L-shapes or rectangles is NP-complete, so one could test other simple shapes for a similar dichotomy.
  • A direct check of the reduction is whether every generated CSP constraint has the declared form z_i ⋄ f(z_j) with the function on the right; if some constraints place monotone counting functions on the left, a minor repair with auxiliary variables would be needed to keep the polynomial-time solver applicable.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper studies boundary covering, where every input point must lie on the boundary of at least one chosen axis-parallel rectangle. It introduces BCDAPR, the discrete variant in which rectangles are chosen from a given family, and proves W[1]-hardness in the parameter k by a reduction from 3-Regular 2-CSP. It then studies BCCAPR, the continuous variant with freely placed rectangles. NP-completeness of BCCAPR is claimed via an intermediate NP-completeness proof for covering points by axis-aligned L-shapes. The paper's main algorithmic claim is an FPT algorithm for BCCAPR with running time 2^{O(k log k)} n^{O(1)}, obtained by enumerating skeletons, endpoint orderings, gap vectors, and exceptional patterns, and reducing each branch to a Distinct Domain Monotone 2-CSP instance solvable in polynomial time.

Significance. If correct, the paper would establish an interesting contrast: discrete rectangle-boundary covering is W[1]-hard while the continuous version is NP-hard yet fixed-parameter tractable for small k. The idea of compressing the geometric interaction into a small number of 'important lines' and then using monotone 2-CSP as a polynomial-time backend is appealing and potentially reusable. The L-shape gadget in Section 5 is also a nice contribution. However, as written the paper contains load-bearing problems in the W[1]-hardness reduction, in the formal validity of the produced CSP instances, and in the running-time count. These issues affect the two main theorems and must be repaired before the paper can be accepted.

major comments (3)
  1. [Section 4.1, variable gadget and Lemma 10] With the natural unit-spaced placement of the points aL_j and aB_j on the square sides, the bottom side of BL_p is the segment from the left side of the square to aB_{p+1}. The constraint points beta^{(ij)}_p are placed between aB_p and aB_{p+1}, so they lie on the bottom side of BL_p and are covered by the variable rectangle selected for assignment a_p. This contradicts the assertion in Lemma 10 that exactly three constraint points are 'not covered by the selected variable rectangles'. Since the soundness argument uses this uncoveredness to force the selected constraint rectangle to match the variable assignment, the reduction as written does not establish Theorem 9. A modified gadget that keeps the beta points off all four selected variable-rectangle sides is needed.
  2. [Section 6.10, constraints (H2), and end of Section 6.11] The definition of Distinct Domain Monotone 2-CSP in Section 3.2 allows only constraints of the form z_i ⋄ f(z_j), with the monotone function applied to the right-hand variable. However, the constructed gap constraints include A_h(coord_h(e_first)) = GapFn(1), A_h(coord_h(e_next^r)) = B_h(coord_h(e_end^r)) + GapFn(r+1), and the symmetric B_h constraints, where the monotone prefix-count functions A_h and B_h are applied to left-hand expressions. These are not of the allowed form. The assertion at the end of Section 6.11 that every constraint is of the form z ⋄ f(z') is therefore false. The issue is repairable by introducing auxiliary variables to hold the values A_h(...) and B_h(...), but as written Proposition 8 is applied to objects that may not be valid CSP instances.
  3. [Section 6.12, Lemma 49] The running-time bound is arithmetically incorrect. Lemma 46 gives k^{O(k)} exceptional-pattern choices per line (because K can be as large as 2k, and each of the K exceptional points has up to 2k choices of rectangle and side). Lemma 37 gives up to (2k)! endpoint orderings per line. Combining the per-line choices over up to 4k lines yields at most (k^{O(k)})^{4k} = k^{O(k^2)} = 2^{O(k^2 log k)} global guesses, not k^{O(k)} as claimed at the end of Lemma 49. The proof would need a global bound on the total number of exceptional incidences over all lines, or a per-line bound of 2^{O(k)}, to justify the advertised 2^{O(k log k)} running time. The algorithm would still be FPT with the weaker bound, but the paper's headline exponent is unsupported as written.
minor comments (5)
  1. [Section 6.2, Lemma 26] The sentence 'by the pigeonhole principle, at least one of |C* ∩ Vvert| or |C* ∩ Vhor| must exceed 2k' is false in general when |C*| > 4k; the two parts could be 3k and k. The lemma's conclusion can be justified directly from the fact that any k-rectangle solution induces a vertex cover of size at most 4k, so the pigeonhole remark should be removed or rewritten.
  2. [Section 6.12, Lemma 49] The text says the total running time is k^{O(k)} · n^{O(1)} while also saying each CSP instance is solved by Proposition 8. For clarity, the proof should explicitly state that the polynomial-time CSP solver is run on each branch and that its cost is included in the n^{O(1)} factor.
  3. [Throughout] The manuscript contains several formatting and typographical artifacts: 'envel⌢pe' in the author affiliation, duplicated Proposition 6/8 numbering, 'CVIT 2016' running headers, and inconsistent use of notation such as 2^{O(klogk)}. These should be corrected in revision.
  4. [Section 5.5, Theorem 24] NP membership of BCCAPR is asserted for rectangles with real coordinates. Since Lemma 25 guarantees a grid-aligned optimal solution, coordinates can be taken from the input point coordinates; this justification should be stated explicitly before Theorem 24.
  5. [Section 3.2, Proposition 8] The paper relies on [1] for the polynomial-time algorithm for Distinct Domain Monotone 2-CSP. Since two authors of the present paper are also authors of [1], a short self-contained proof or at least a precise statement of the algorithm's invariant would strengthen the presentation and make the reduction self-contained.

Circularity Check

0 steps flagged

No circular derivation chain found.

full rationale

The paper's derivations are reductions: BCDAPR W[1]-hardness from 3-Regular 2-CSP (Section 4), LSC/BCCAPR NP-hardness from CBVC and NE-LSC (Section 5), and the BCCAPR FPT algorithm as a parameterized reduction to Distinct Domain Monotone 2-CSP (Section 6). In each reduction the constructed objects are defined from the input instance, not from the target answer, and the proof of Lemma 48 gives a bijective correspondence between rectangle covers and CSP assignments. The only author-overlap dependency is Proposition 8 ([1]), the polynomial-time solver for the CSP; this is an external published theorem with assumptions independent of BCCAPR, so it is support rather than a circular step. The two substantive objections in the review are correctness failures, not circularity: (a) constraints such as A_h(coord_h(e_first)) = GapFn(1) in (H2) are not of the allowed form z_i ⋄ f(z_j) unless auxiliary variables are added, so the instance may not be a valid Distinct Domain Monotone 2-CSP as written; and (b) Lemma 49 multiplies per-line k^{O(k)} guesses over 4k lines, yielding k^{O(k^2)} absent a global O(k) bound on exceptional incidences. Neither of these makes the target theorem an input by construction, so no circular step can be exhibited.

Axiom & Free-Parameter Ledger

0 free parameters · 4 axioms · 0 invented entities

No numerical fitting is involved; all construction parameters such as M=k+1 or M=2k+1 are structural choices, not fitted values. The central claims rest on cited hardness results, the cited monotone-CSP algorithm, and the internal correctness of the geometric gadgets.

axioms (4)
  • domain assumption Distinct Domain Monotone 2-CSP is solvable in polynomial time
    Proposition 8, cited to [1] (Agrawal et al.), partly co-authored by current authors. The FPT algorithm depends on this subroutine, and the paper does not provide a proof or formalization.
  • domain assumption 3-Regular 2-CSP is W[1]-hard parameterized by number of variables
    Proposition 7, cited to [4,12]. Used as the source problem for the W[1]-hardness reduction.
  • domain assumption Constrained Bipartite Vertex Cover is NP-complete
    Used in the NP-hardness reduction to L-Shape Cover; cited to [10].
  • standard math Minimum vertex cover in bipartite graphs is polynomial-time computable via Kőnig's theorem
    Used in Lemma 26 to compute the set ImpLines in polynomial time.

reviewed 2026-08-02 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Covering Points with Rectangular Boundaries." pith.science (2026). https://pith.science/paper/H2EDXKTK

@misc{pith2026260708183,
  author       = {Pith},
  title        = {Pith review of: Covering Points with Rectangular Boundaries},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/H2EDXKTK}},
  note         = {Machine review of arXiv:2607.08183}
}
Share X Bluesky LinkedIn Reddit HN
abstract

Geometric covering problems ask for a small family of geometric objects whose union covers a given point set. We study the more restrictive \emph{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 \emph{discrete} setting, where rectangles must be selected from a given family. We define \bcdaprfull\ (\bcdaprshort): given a point set \(P\subseteq\mathbb{R}^2\), a family \(\mathcal{R}\) of axis-parallel rectangles, and an integer \(k\), decide whether \(P\) can be covered by the boundaries of at most \(k\) rectangles from \(\mathcal{R}\). We prove that \bcdaprshort\ is \(\mathrm{W}[1]\)-hard parameterized by \(k\). We then study the \emph{continuous} variant, \prbcfull\ (\prbcshort), where rectangles may be placed freely. Given \(P\subseteq\mathbb{R}^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(k\log k)}\cdot 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(k\log 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.

Figures

Figures reproduced from arXiv: 2607.08183 by Daniel Lokshtanov, Kushal Singanporia, Madhumita Kundu, Saket Saurabh, Soumi Nandi.

Figure 9
Figure 9. Figure 9: 1. Aligned coverage: A point p ∈ PL is said to be aligned covered by a rectangle R if the line L coincides with either the top or the bottom side of R, and the point p lies on that side of R. C V I T 2 0 1 6 [PITH_FULL_IMAGE:figures/full_fig_p025_9.png] view at source ↗
Figure 9
Figure 9. Figure 9: {p1, . . . , p8} are the points along a horizontal line L. Coverage of p1, p2, p3 by R1 is example of aligned coverage where as coverage of p5, p6 by R2 is crossing coverage. 1. bd(R) ∩ L = ∅ (this happens when yL ∈/ [c, d]); 2. L coincides with a horizontal side of R (i.e., yL ∈ {c, d}), and then bd(R) ∩ L = [a, b] × {yL}; 3. c < yL < d, and then bd(R) ∩ L = {(a, yL),(b, yL)}. In particular, if no horizon… view at source ↗

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

25 extracted references

  1. [1]

    2015 , date =

    John Baez , title =. 2015 , date =

    2015

  2. [2]

    Knuth , title =

    Donald E. Knuth , title =. Commun. 1974 , doi =

    1974

  3. [3]

    Dijkstra , title =

    Edsger W. Dijkstra , title =. Commun. 1968 , doi =

    1968

  4. [4]

    1993 , isbn =

    Jim Gray and Andreas Reuter , title =. 1993 , isbn =

    1993

  5. [5]

    1975 , crossref =

    On Time versus Space and Related Problems , booktitle =. 1975 , crossref =. doi:10.1109/SFCS.1975.23 , timestamp =

    doi:10.1109/sfcs.1975.23 1975

  6. [6]

    1975 , timestamp =

    16th Annual Symposium on Foundations of Computer Science, Berkeley, California, USA, October 13-15, 1975 , publisher =. 1975 , timestamp =

    1975

  7. [7]

    Covering points by axis parallel lines , author=. Proc. 23rd European Workshop on Computational Geometry , pages=

  8. [8]

    Refael Hassin and Nimrod Megiddo , title =. Discret. Appl. Math. , volume =. 1991 , url =. doi:10.1016/0166-218X(91)90011-K , timestamp =

    doi:10.1016/0166-218x(91)90011-k 1991

  9. [9]

    2008 , publisher=

    Combinatorial optimization: theory and algorithms , author=. 2008 , publisher=

    2008

  10. [10]

    Stefan Langerman and Pat Morin , title =. Discret. Comput. Geom. , volume =. 2005 , url =. doi:10.1007/S00454-004-1108-4 , timestamp =

    doi:10.1007/s00454-004-1108-4 2005

  11. [11]

    Efficient Approximation Schemes for Geometric Problems? , booktitle =

    D. Efficient Approximation Schemes for Geometric Problems? , booktitle =. 2005 , url =. doi:10.1007/11561071\_41 , timestamp =

    doi:10.1007/11561071 2005

  12. [13]

    Fixed Parameter Tractability of Independent Set in Segment Intersection Graphs , booktitle =

    Jan K. Fixed Parameter Tractability of Independent Set in Segment Intersection Graphs , booktitle =. 2006 , url =. doi:10.1007/11847250\_15 , timestamp =

    doi:10.1007/11847250 2006

  13. [14]

    Sergio Cabello and Panos Giannopoulos and Christian Knauer , title =. Inf. Process. Lett. , volume =. 2008 , url =. doi:10.1016/J.IPL.2007.08.003 , timestamp =

    doi:10.1016/j.ipl.2007.08.003 2008

  14. [15]

    Panos Giannopoulos and Christian Knauer and Sue Whitesides , title =. Comput. J. , volume =. 2008 , url =. doi:10.1093/COMJNL/BXM053 , timestamp =

    doi:10.1093/comjnl/bxm053 2008

  15. [16]

    IEEE Design & Test of Computers , volume=

    Efficient spare allocation for reconfigurable arrays , author=. IEEE Design & Test of Computers , volume=. 2007 , publisher=

    2007

  16. [17]

    Parameterized and Approximation Algorithms for Coverings Points with Segments in the Plane , booktitle =

    Katarzyna Anna Kowalska and Michal Pilipczuk , editor =. Parameterized and Approximation Algorithms for Coverings Points with Segments in the Plane , booktitle =. 2024 , url =. doi:10.4230/LIPICS.STACS.2024.47 , timestamp =

    doi:10.4230/lipics.stacs.2024.47 2024

  17. [18]

    Akanksha Agrawal and Kristine V. K. Knudsen and Daniel Lokshtanov and Saket Saurabh and Meirav Zehavi , title =. Discret. Comput. Geom. , volume =. 2024 , url =. doi:10.1007/S00454-023-00569-Y , timestamp =

    doi:10.1007/s00454-023-00569-y 2024

  18. [19]

    Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams , journal =

    D. Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams , journal =. 2022 , url =. doi:10.1145/3483425 , timestamp =

    doi:10.1145/3483425 2022

  19. [20]

    2016 , url =

    Stefan Kratsch and Geevarghese Philip and Saurabh Ray , title =. 2016 , url =. doi:10.1145/2832912 , timestamp =

    doi:10.1145/2832912 2016

  20. [21]

    1975 , volume =

    László Lovász , title =. 1975 , volume =

    1975

  21. [22]

    Combinatorica , year =

    Ron Aharoni and Ron Holzman and Michael Krivelevich , title =. Combinatorica , year =. doi:10.1007/BF01844843 , url =

    doi:10.1007/bf01844843

  22. [23]

    Parameterized Complexity and Approximation Algorithms , journal =

    D. Parameterized Complexity and Approximation Algorithms , journal =

  23. [24]

    Daniel Lokshtanov and M. S. Ramanujan and Saket Saurabh and Meirav Zehavi , editor =. Parameterized Complexity and Approximability of Directed Odd Cycle Transversal , booktitle =. 2020 , url =. doi:10.1137/1.9781611975994.134 , timestamp =

    doi:10.1137/1.9781611975994.134 2020

  24. [25]

    Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis , booktitle =

    Venkatesan Guruswami and Bingkai Lin and Xuandi Ren and Yican Sun and Kewen Wu , editor =. Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis , booktitle =. 2024 , url =. doi:10.1145/3618260.3649771 , timestamp =

    arXiv 2024

  25. [26]

    Hopcroft and R

    J. Hopcroft and R. Karp,

This paper was first reviewed by deepseek-v4-flash on August 2, 2026.