On The Computational Complexity of Minimum Aerial Photographs for Planar Region Coverage

Si Wei Feng

REVIEW 5 major objections 4 minor 12 references

On The Computational Complexity of Minimum Aerial Photographs for Planar Region Coverage

T0 review · 5 major / 4 minor · reviewed 2026-08-03 · deepseek-v4-flash

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

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2512.18268 v3 pith:IY62CUGP submitted 2025-12-20 cs.RO cs.CG

Si Wei Feng This is my paper · ORCID

classification cs.ROcs.CG MSC 68Q1768U05

keywords NP-hardnessinapproximabilitysquarecoveragepolygonvertexcoverreductiongeometriccoveringaerialphotographyapproximationalgorithm

topics P versus NP

open problems P versus NP

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

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.

What carries the argument

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

What would settle it

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.

Watch

Extended reading notes

Core claim

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

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Colleague,

Quick 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.

What'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.

The 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.

Worse, 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.

So 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.

Who 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.

Recommendation: 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.

Referee Report

5 major / 4 minor

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.

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 (5)

[Hardness of approximate square coverage (Theorem 2)] 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.
[Restricted-center square coverage, Eqs. (14)-(17)] 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.
[Hardness of approximate square coverage, reduction count] 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.
[Constant factor approximation algorithm (Algorithm 1)] 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.
[Hardness of approximate coverage with restricted locations (Theorem 3)] 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.

minor comments (4)

[Problem formulations] 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.
[Remark 1 and Remark 2] 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.
[Figures] 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.
[Equations (7)-(13)] 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.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity; square inapproximability constants are solved from geometric constraints rather than fitted, and the main derivation does not reduce to its inputs. Score 2 reflects a self-cited prior circle result and an unproved pattern-classification lemma (correctness gap, not circularity).

full rationale

The central square-hardness argument reduces Planar Cubic Vertex Cover (Mohar 2001) to covering the gadget T_G with k squares. The gap constants 1.165 and 1.25 are obtained by solving explicit geometric constraint systems (Eqs. 7-13 for the unrestricted junction, Eqs. 14-17 for the restricted junction, with 1.25 taken as the minimum of the junction bound and the path-pattern bound in Figure 6). These constants are not fit to the desired inapproximability answer, and no prediction is statistically or definitionally forced. The reverse direction of the reduction depends on an asserted pattern-classification lemma: the text states without proof that, below the threshold, the only square-cover patterns to consider are those in Figures 5, 8 and 9; this is an omitted proof / correctness risk, not a circular step, because it does not assume the theorem it is used to prove. The circle-hardness section (Theorem 1) is explicitly attributed to the author's prior work (Feng and Yu 2020); that self-citation supplies the circle pattern classification, but the new square results do not reduce to it and instead introduce independent geometry (shrunk unit segments, zeta = sqrt(2)/2, junction distance 3sqrt(2)/4). As a separate non-circular correctness concern, the printed equations for the restricted case appear internally inconsistent: combining (16) and (17) gives sqrt(2)*ell + ||CQ|| = 5sqrt(2)/4, which with ell = 1.289 already exceeds the right-hand side, so the claimed ell = 1.289 cannot follow as written. This affects the reliability of Theorem 4 but is not a self-referential or fitted-input circularity. The 2.828 approximation factor follows from a standard 2-approximate L-infinity farthest clustering step plus a geometric sqrt(2) bound for rotating squares, independent of the hardness results. Overall, no step in the derivation chain is equivalent to its inputs by construction; the score is set to 2 for the self-citation reliance and the unproved classification assertion, both of which are correctness/evidence concerns rather than circular reductions.

Assumptions & free parameters 5 free parameters · 5 assumptions · 0 invented entities

The central claims rest on the NP-hardness of a graph problem, a geometric embedding that is assumed without proof, and an unproved canonical-coverage-pattern lemma; the constants in the construction are chosen by hand to tune the thresholds.

free parameters (5)

bar length ζ for circle construction = √3
Chosen by hand in the gadget to make the junction pattern analysis yield the 1.152 circle gap; entered at 'First, we set the bar length ζ=√3 in the gadget structure.'
bar length ζ for square construction = √2/2
Chosen for the square gadget; the unit segment length is also shrunk to √2/2 so the perpendicular bar spacing drives the 1.165/1.25 thresholds.
junction distance = 3√2/4
Distance between the crossing point and neighboring vertical bar at the tri-connected junction; set by hand in the square construction.
thickening width ε = →0
The gadget is converted to a simple polygon by dilating with width ε; the hardness transfer depends on the limit, not an actual positive width.
sampling density ε in Algorithm 1 = unspecified
Algorithm 1 samples N points with density ϵ; the exact ϵ needed for the (2√2+ϵ) guarantee is not specified.

assumptions (5)

standard math Vertex Cover on Planar Cubic Graph is NP-hard (Mohar 2001)
The reduction starts from this problem; cited at Problem 4.
domain assumption The planar cubic graph can be embedded with 120° junction angles and odd-length nearly-straight paths
Stated in 'Intermediate structure construction' without proof; needed for the gadget to be simple and coverage patterns to match.
ad hoc to paper Canonical coverage-pattern lemma: for side length below the threshold, every optimal junction/path cover follows Figures 5/8/9
The entire hardness transfer rests on this unstated exhaustive-case lemma; the paper only analyzes one pattern and does not rule out alternatives.
domain assumption Boundary/interior coverage equivalence via ε-thickening with δ→0
Remark 1 asserts the equivalence; it is plausible but unquantified.
standard math Gonzalez farthest clustering gives a 2-approximation for k-center in L∞
Used for the 2.828 algorithm; cited to Gonzalez 1985.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On The Computational Complexity of Minimum Aerial Photographs for Planar Region Coverage." pith.science (2026). https://pith.science/paper/IY62CUGP

@misc{pith2026251218268,
  author       = {Pith},
  title        = {Pith review of: On The Computational Complexity of Minimum Aerial Photographs for Planar Region Coverage},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IY62CUGP}},
  note         = {Machine review of arXiv:2512.18268}
}

abstract

With the popularity of drone technologies, aerial photography has become prevalent in many daily scenarios such as environment monitoring, structure inspection, law enforcement etc. A central challenge in this domain is the efficient coverage of a target area with photographs that can entirely capture the region, while respecting constraints such as the image resolution, and limited number of pictures that can be taken. This work investigates the computational complexity of covering a simple planar polygon using squares and circles. Specifically, it shows inapproximability gaps of $1.165$ (for squares) and $1.25$ (for restricted square centers) and develops a $2.828$-optimal approximation algorithm, demonstrating that these problems are computationally intractable to approximate. The intuitions of this work can extend beyond aerial photography to broader applications such as pesticide spraying and strategic sensor placement.

Figures

Figures reproduced from arXiv: 2512.18268 by the authors.

**Figure 2.** Structure within the odd length path and attached [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

**Figure 5.** Structure within the odd length path, where each [PITH_FULL_IMAGE:figures/full_fig_p004_5.png] view at source ↗

Figures from the paper (4 more)

**Figure 6.** Figure 6: Possible square coverage pattern along the con [PITH_FULL_IMAGE:figures/full_fig_p004_6.png]

**Figure 4.** Figure 4: Circle coverage pattern at the extreme circle radius [PITH_FULL_IMAGE:figures/full_fig_p004_4.png]

**Figure 7.** Figure 7: Square coverage pattern at the junction crossing [PITH_FULL_IMAGE:figures/full_fig_p005_7.png]

**Figure 8.** Figure 8: The pattern of covering the crossing in the special [PITH_FULL_IMAGE:figures/full_fig_p005_8.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references

[1]

Feder, T.; and Greene, D. 1988. Optimal algorithms for ap- proximate clustering. InProceedings of the twentieth annual ACM symposium on Theory of computing, 434–444

1988
[2]

W.; Gao, K.; Gong, J.; and Yu, J

Feng, S. W.; Gao, K.; Gong, J.; and Yu, J. 2021. Sensor placement for globally optimal coverage of 3d-embedded surfaces. In2021 IEEE International Conference on Robotics and Automation (ICRA), 8600–8606. IEEE

2021
[3]

W.; Han, S

Feng, S. W.; Han, S. D.; Gao, K.; and Yu, J. 2019. Effi- cient algorithms for optimal perimeter guarding. In2019 Robotics: Science and Systems

2019
[4]

W.; and Yu, J

Feng, S. W.; and Yu, J. 2020. Optimally Guarding Perime- ters and Regions with Mobile Range Sensors. In2020 Robotics: Science and Systems

2020
[5]

Gage, D. W. 1992. Command control for many-robot sys- tems.Unmanned Systems Magazine, 10(4): 28–34

1992
[6]

Gonzalez, T. F. 1985. Clustering to minimize the maxi- mum intercluster distance.Theoretical computer science, 38: 293–306

1985
[7]

S.; and Maass, W

Hochbaum, D. S.; and Maass, W. 1985. Approximation schemes for covering and packing problems in image pro- cessing and VLSI.Journal of the ACM (JACM), 32(1): 130– 136

1985
[8]

P.; Paprocki, M.; ˇCert´ık, O.; Kir- pichev, S

Meurer, A.; Smith, C. P.; Paprocki, M.; ˇCert´ık, O.; Kir- pichev, S. B.; Rocklin, M.; Kumar, A.; Ivanov, S.; Moore, J. K.; Singh, S.; et al. 2017. SymPy: symbolic computing in Python.PeerJ Computer Science, 3: e103

2017

Show all 12 references

[9]

Mohar, B. 2001. Face covers and the genus problem for apex graphs.Journal of Combinatorial Theory, Series B, 82(1): 102–117

2001
[10]

Optimization, G. 2019. Gurobi Optimizer 9.0.Gurobi: http://www.gurobi.com

2019
[11]

Kapoor, A.; Hanrahan, P.; and Joshi, N. 2017. Submodular trajectory optimization for aerial 3d scanning. InProceed- ings of the IEEE International Conference on Computer Vi- sion, 5324–5333

2017
[12]

D.; O’Rourke, J.; and Goodman, J

Toth, C. D.; O’Rourke, J.; and Goodman, J. E. 2017.Hand- book of discrete and computational geometry. CRC press

2017

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.

[1] [1]

Feder, T.; and Greene, D. 1988. Optimal algorithms for ap- proximate clustering. InProceedings of the twentieth annual ACM symposium on Theory of computing, 434–444

1988

[2] [2]

W.; Gao, K.; Gong, J.; and Yu, J

Feng, S. W.; Gao, K.; Gong, J.; and Yu, J. 2021. Sensor placement for globally optimal coverage of 3d-embedded surfaces. In2021 IEEE International Conference on Robotics and Automation (ICRA), 8600–8606. IEEE

2021

[3] [3]

W.; Han, S

Feng, S. W.; Han, S. D.; Gao, K.; and Yu, J. 2019. Effi- cient algorithms for optimal perimeter guarding. In2019 Robotics: Science and Systems

2019

[4] [4]

W.; and Yu, J

Feng, S. W.; and Yu, J. 2020. Optimally Guarding Perime- ters and Regions with Mobile Range Sensors. In2020 Robotics: Science and Systems

2020

[5] [5]

Gage, D. W. 1992. Command control for many-robot sys- tems.Unmanned Systems Magazine, 10(4): 28–34

1992

[6] [6]

Gonzalez, T. F. 1985. Clustering to minimize the maxi- mum intercluster distance.Theoretical computer science, 38: 293–306

1985

[7] [7]

S.; and Maass, W

Hochbaum, D. S.; and Maass, W. 1985. Approximation schemes for covering and packing problems in image pro- cessing and VLSI.Journal of the ACM (JACM), 32(1): 130– 136

1985

[8] [8]

P.; Paprocki, M.; ˇCert´ık, O.; Kir- pichev, S

Meurer, A.; Smith, C. P.; Paprocki, M.; ˇCert´ık, O.; Kir- pichev, S. B.; Rocklin, M.; Kumar, A.; Ivanov, S.; Moore, J. K.; Singh, S.; et al. 2017. SymPy: symbolic computing in Python.PeerJ Computer Science, 3: e103

2017