{"id":"61b6b886-ddff-47ce-9968-e43f59bd70f7","arxiv_id":"2512.18268","paper_version":3,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":5,"one_line_summary":"Covering a simple polygon with k equal squares is claimed NP-hard to approximate within factor 1.165 (or 1.25 with centers restricted to the polygon), with a 2.828-approximation algorithm.","lead":"This paper claims to prove that choosing the smallest square camera footprint to cover a planar region with k photos is NP-hard to approximate within 16.5%, and that a simple clustering rule gets within 2.83× of optimal. The proof is a sketch and a supporting equation set appears internally inconsistent, so the result is not yet established.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The square-cover hardness proof depends on an unproved classification lemma: no proof rules out alternative junction/edge cover patterns below the claimed thresholds, and the restricted-case equations do not even yield ℓ=1.289.","rationale":"The reader's weakest assumption is exactly the load-bearing gap. The high-level reduction strategy follows the circle-coverage paper, but the square case introduces new complications: rotated squares, continuous placement, and junction geometry. The proof of the gap essentially consists of Figures 5–9 and the phrase 'listing all necessary geometric constraints.' That phrase is doing the work of a classification lemma: one must know, for all ℓ below threshold, the complete list of possible minimal square arrangements on the gadget. The paper never states this list, let alone proves its completeness. The approximation algorithm and the circle result are independent support for the general framework, and I do not question them; the problem is specific to the square-hardness claim. The restricted-case equations being inconsistent with ℓ=1.289—from (16) and (17), √2ℓ + ∥CQ∥ = 5√2/4 forces ∥CQ∥<0 at ℓ=1.289—shows the pattern-based threshold calculations are fragile. A single counterexample to the canonical pattern, or a rigorous enumeration establishing it, would settle the question. Since neither is present, the central hardness claims are not established; the paper cannot be accepted as a proof. This leaves the reader's rejection unchanged.","tokens_in":8008,"tokens_out":8320,"duration_ms":83910,"concrete_test":"Use an exact/interval SMT search for one three-branch junction: three congruent squares of side ℓ<1.165, arbitrary centers and orientations, required to cover the junction and the adjacent portions of the three incident edge/bar segments used in Fig. 8. Ask whether any cover has an incidence pattern different from the claimed canonical one. A witness would falsify the reduction; a rigorous unsatisfiability certificate would supply the missing classification lemma for the junction.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorems 2 and 4 stand or fall on a lemma that the text never states: for square side length ℓ below the claimed thresholds, every minimum cover of the gadget T_G with n+M squares must realize the odd/even endpoint assignments that encode a vertex cover of G. The derivation only exhibits one junction pattern (Figs. 8/9) and one pair of edge patterns (Figs. 5/6), then says 'listing all necessary geometric constraints' yields ℓ=1.165 (Eqs. 7–13) and ℓ=1.289 (Eqs. 14–17). This is not a classification proof. Squares may be rotated arbitrarily, centers may lie anywhere, and a single square may cover parts of more than one bar or even of two incident edges; the text does not enumerate the finite set of incidence patterns or rule out alternatives by a geometric argument. Without that lemma, the reverse direction—an n+M-square cover of side <1.165 implies a vertex cover of size n—does not follow, so the inapproximability reduction is incomplete. The concern is not merely 'more detail needed': for the restricted case the written equations are internally inconsistent. Combining (16) and (17) gives √2 ℓ + ∥CQ∥ = 5√2/4; with ℓ=1.289 the first term already exceeds the right-hand side, so no positive ∥CQ∥ exists. This indicates the pattern-derived thresholds are not reliable as printed.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the computational complexity of covering a simple polygon with k congruent squares or circles, motivated by aerial photography. It claims an inapproximability gap of 1.165 for the minimum-side-length square coverage problem (Theorem 2), a 1.25 gap for the restricted-center variant (Theorem 4), and a 2.828-approximation algorithm for square coverage. The hardness proofs adapt the author's prior circle-cover construction by converting a planar cubic graph into a thin 'tri-net' gadget with attached bars, then reducing vertex cover to covering the gadget with n+M unit squares. The paper also treats restricted-center variants and sketches an approximation algorithm based on farthest clustering with the L∞ metric.","tokens_in":8423,"tokens_out":5974,"duration_ms":55382,"significance":"If the claimed inapproximability gaps were rigorously established, the paper would be a useful extension of the circle-coverage result of Feng and Yu to square footprints, bringing the hardness result closer to practical camera models. The restricted-center variant is also a natural problem. However, the manuscript as written does not establish the central theorems: the square-cover hardness proof is missing a geometric classification lemma that is essential to the reduction, and the restricted-case equations are internally inconsistent. The approximation algorithm also lacks a rigorous sampling/density argument. The paper's contribution is therefore currently not supported.","major_comments":[{"comment":"The proof requires a classification lemma: for square side length below 1.165, every minimum cover of the gadget T_G must realize one of the patterns in Figures 5/6 and 7/8, so that the odd/even endpoint assignments encode a vertex cover. No such lemma is stated or proved. The text analyzes one junction pattern and then asserts that 'listing all necessary geometric constraints' in Eqs. (7)-(13) gives ℓ=1.165. This does not rule out squares with arbitrary rotations, centers lying inside bars, or squares covering parts of multiple bars or two incident edges. Without that classification, the direction 'an (n+M)-square cover of side <1.165 implies a vertex cover of size n' does not follow, and the NP-hardness reduction is incomplete.","section":"Hardness of approximate square coverage (Theorem 2)"},{"comment":"The displayed system for the restricted junction pattern is internally inconsistent. Combining (16) and (17) gives ∥CQ∥ + √2ℓ = 5√2/4. Since 5√2/4 ≈ 1.768 and √2ℓ at ℓ=1.289 is ≈ 1.823, no positive ∥CQ∥ can satisfy both equations. Thus the claimed solution ℓ=1.289 cannot be correct, and Theorem 4, which relies on this value to derive the 1.25 gap, is unsupported as printed.","section":"Restricted-center square coverage, Eqs. (14)-(17)"},{"comment":"The reduction states that a vertex cover of size n leads to a cover with n+M unit squares, but M is never defined. The gadget contains many paths, bars, and junctions; it is not clear whether M counts edges of the original graph, subdivided path segments, or something else. The equivalence between vertex-cover size and covering number is therefore not well-posed. A precise statement of M and a proof of the counting in both directions are needed before Theorem 2 can be assessed.","section":"Hardness of approximate square coverage, reduction count"},{"comment":"The claimed (2√2 + ε)-approximation is not established. The argument that an arbitrary rotated square of side ℓ is contained in an axis-aligned square of side √2ℓ is correct, but the algorithm covers a finite sample, not the continuous polygon. No density or Lipschitz argument is supplied to show that covering the sampled points with L∞ farthest clustering yields coverage of the entire polygon within the stated error. Since the algorithm also restricts centers to sampled points, its approximation guarantee for the original continuous problem is not immediate.","section":"Constant factor approximation algorithm (Algorithm 1)"},{"comment":"The proof of the restricted circle-coverage bound is a single sentence: unit-circle covers of the construction can be made centered on the skeleton 'until the circle radius reaches 1.152.' This is not obvious, because the centers in the unconstrained construction may lie in the interior of the solidified polygon rather than on the skeleton. A detailed argument that the centers can be moved onto the skeleton without increasing the number of circles is required.","section":"Hardness of approximate coverage with restricted locations (Theorem 3)"}],"minor_comments":[{"comment":"The symbol n is overloaded: it appears as a vertex-cover size parameter in Problem 4, as the number of vertices in the reduction, and as part of the square count n+M. The paper should use distinct notations (e.g., ν for vertex-cover size, k for number of squares) to avoid confusion.","section":"Problem formulations"},{"comment":"The claimed equivalence between covering the boundary and covering the interior of a polygon is stated informally ('at the same level'). This is a nontrivial reduction; a precise statement with the required width δ and error analysis would strengthen the paper.","section":"Remark 1 and Remark 2"},{"comment":"Figures 5, 6, 7, 8, and 9 are dense and hard to read; important points (e.g., C, Q, F, G, I, J) are difficult to locate. It would help to label coordinates and angles, and to provide a separate schematic of the different coverage patterns.","section":"Figures"},{"comment":"The paper says the equations were solved with Sympy but does not provide the derivation or the numerical code. Since the constant 1.165 is a central claim, a reproducible symbolic/numeric verification or at least an algebraic elimination showing uniqueness of ℓ would be desirable.","section":"Equations (7)-(13)"}],"recommendation":"reject","confidential_remarks":"The manuscript appears to be a preliminary write-up of an extension of the author's prior work. The main theorems are not proved in the current text: the square-cover reduction lacks a classification lemma, the restricted-case equations are numerically inconsistent, and the approximation algorithm is missing a sampling/density argument. These are not presentation issues but load-bearing gaps. Should a substantially revised version supply a complete classification lemma and corrected constants, the editor may wish to consider it afresh."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nQuick take: the paper's central claim—NP-hard to approximate square coverage of a simple polygon within 1.165—is plausible but not proven. The reduction follows the author's earlier circle result, but the key step, that any n+M-square cover below the threshold must use the junction/edge patterns that encode a vertex cover, is asserted rather than demonstrated. The text says 'listing all necessary geometric constraints' and jumps to the constant. That's not a proof.\n\nWhat's actually new: the square-oriented gadget is a genuine extension of the circle construction, and the claimed thresholds are new for this problem. The approximation algorithm is a routine but valid combination: sample points, run k-center with L∞ (2-approx), inflate to squares (√2 factor), giving 2.828. That part is solid.\n\nThe soft spots are in the hardness proofs. The missing lemma is the load-bearing one: with arbitrary square orientations, you need a classification of all possible ways a square can cover parts of bars and junctions below the threshold. Without that, the reduction's reverse direction doesn't go through. The author only exhibits one pattern and asserts exclusivity.\n\nWorse, the restricted case's equations (14)–(17) are internally inconsistent as printed. Combining (16) and (17) gives √2ℓ + ||CQ|| = 5√2/4. At ℓ=1.289 the first term alone is about 1.823, exceeding the RHS 1.768, so no positive ||CQ|| exists. The claimed 1.289 cannot be derived from these equations. That's not a minor typo; it indicates either a wrong diagram or wrong equations.\n\nSo the main hardness theorems are not established in this version. The high-level idea might be salvageable—if the missing classification lemma can be proved and the equations fixed—but that's real work.\n\nWho should read it: researchers in computational geometry or drone coverage who want to know the state of the art. It's not a paper to cite for the hardness results yet.\n\nRecommendation: send to peer review if you think the area warrants it—the idea is worth a careful referee's time to see if the gap is repairable. But if this is for a quick decision, reject as is. The approximation algorithm alone doesn't carry the paper.","headline":"The square-cover inapproximability proof has a load-bearing gap: no classification lemma rules out alternative patterns, and the restricted-case equations don't even solve to the claimed 1.289.","tokens_in":8843,"tokens_out":2459,"would_cite":false,"duration_ms":22899,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68U05"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that covering a simple planar polygon with k squares is NP-hard to approximate within a factor of 1.165, and within 1.25 when square centers are restricted to the region.","keywords":["NP-hardness","inapproximability","square coverage","polygon coverage","vertex cover reduction","geometric covering","aerial photography","approximation algorithm"],"falsifier":"Exhaustively search, e.g., by discretizing positions and orientations, for a cover of the tri-net junction with side length below 1.165 that uses fewer than three squares, or that uses three squares but in a configuration not equivalent to the claimed patterns; finding one would invalidate the vertex-cover equivalence. A purely analytic alternative is to show the system (7)–(13) admits another geometric solution below 1.165.","tokens_in":7899,"feed_emoji":"📷","tokens_out":4511,"duration_ms":43943,"temperature":0.7,"pith_summary":"This paper asks how hard it is to find the smallest square side length ℓ such that k squares can cover a simple planar polygon, the footprint model for a downward-facing drone camera. The paper proves that unless P=NP, no polynomial-time algorithm can approximate that ℓ within a factor of 1.165 for squares, and within 1.25 when square centers must lie inside the region. It also gives a (2.828+ε)-approximation algorithm based on farthest clustering under the L∞ metric, leaving a wide gap between hardness and tractability. These results transfer to circle coverage with a known 1.152 gap, and put aerial photography coverage problems on firm computational footing.","feed_headline":"Covering a polygon with k squares: no 1.165-approximation","feed_subtitle":"Unless P=NP, no polynomial-time algorithm can guarantee a square side length within 16.5% of optimal for aerial coverage.","key_machinery":"The reduction gadget: a planar cubic graph is embedded so edges become odd-length unit paths meeting at 120° junctions, and each unit segment is crossed by a perpendicular bar of length ζ; after shrinking unit steps to √2/2 and setting ζ=√2/2, the polygon's skeleton becomes a 'tri-net'. The load-bearing identity is the claimed equivalence: for square side length below 1.165, every minimum cover of a junction uses exactly three squares in the patterns of Figures 5 and 8, making the global minimum cover equivalent to a vertex cover. A system of geometric equations (7)–(13) is solved with symbolic algebra to get the threshold ℓ=1.165 (and (14)–(17) for the constrained variant giving 1.289 cappe","core_discovery":"The central claim is that minimum-side-length coverage of a simple polygon by k squares is inapproximable: any polynomial-time algorithm that always returns a square side length below 1.165 times the optimum would imply P=NP. The proof reduces Vertex Cover on planar cubic graphs to the coverage problem by constructing a polygon whose 'tri-net' skeleton consists of odd-length paths with perpendicular bars; below the threshold side length, covering the structure with unit squares forces each junction to be covered in one of two canonical patterns, so the minimum number of squares equals the minimum vertex cover size. The same construction, with center constraints, yields a 1.25 inapproximabili","pith_inferences":["The claimed 1.165 threshold rests on an unverified exhaustive classification of junction cover patterns; a computational search over square arrangements could confirm or refute the threshold, and if refuted the current factor would need revision.","The wide gap between 1.165 and 2.828 suggests there may be stronger inapproximability results or better approximation algorithms; the constant 2.828 likely improvable by directly optimizing square orientation instead of using axis-aligned squares.","The reduction uses a planar cubic graph vertex cover, known NP-hard; applying the same gadget to other hard problems (e.g., independent set on cubic graphs) might yield different factors.","For practical drone flight planning, the hardness result implies that heuristics based on clustering and sampling are not just conveniences but necessary trade-offs."],"forward_implications":["Drone operators cannot optimally set camera zoom to cover a region with k images in polynomial time; approximation is the best one can guarantee.","The 1.165 gap means any practical planner must either relax optimality or use exponential-time methods for moderate k, e.g., integer programming on sampled point sets.","The 2.828-approximation gives a concrete, implementable algorithm with a constant-factor guarantee for square footprints, extending to constrained centers.","The boundary vs. interior coverage equivalence links perimeter guarding and region coverage at the same hardness level."],"fun_headline_variants":["Polygon square coverage: no 1.165-approximation unless P=NP","Aerial photography coverage is hard to approximate beyond 1.165","Minimum photos for a region: inapproximable gap of 1.165","Square coverage of polygons: approximation hardness proven","Drone photo planning: 1.165-approximation impossible (P≠NP)"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The proof assumes that for square side length below 1.165, every minimum cover of the constructed tri-net junction must consist of exactly the three-square patterns shown in Figures 5 and 8, and that no alternative arrangement can cover the junction with fewer squares; this canonical-pattern classification is asserted after listing one pattern's equations rather than proved.","fun_headline_variants_meta":{"raw":{"variants":["Polygon square coverage: no 1.165-approximation unless P=NP","Aerial photography coverage is hard to approximate beyond 1.165","Minimum photos for a region: inapproximable gap of 1.165","Square coverage of polygons: approximation hardness proven","Drone photo planning: 1.165-approximation impossible (P≠NP)"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000457,"raw_usage":{"total_tokens":2091,"prompt_tokens":668,"completion_tokens":1423,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":412,"completion_tokens_details":{"reasoning_tokens":1326}},"tokens_in":412,"tokens_out":1423,"duration_ms":13056,"temperature":1.0,"reasoning_tokens":1326,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T15:03:03.385708+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhaustively search, e.g., by discretizing positions and orientations, for a cover of the tri-net junction with side length below 1.165 that uses fewer than three squares, or that uses three squares but in a configuration not equivalent to the claimed patterns; finding one would invalidate the vertex-cover equivalence. A purely analytic alternative is to show the system (7)–(13) admits another geometric solution below 1.165.","supporting_citations":[],"review_version":1}