Pith. sign in

REVIEW 3 major objections 4 minor 17 references

Guarding Terrains with Guards on a Line

T0 review · 3 major / 4 minor · reviewed 2026-08-16 · deepseek-v4-flash

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

Pith's one-line read Exact algorithms place k point guards on the lowest horizontal line that covers an x-monotone terrain, and an O(kn) bijective variant.

desk verdict A genuinely new algorithmic result for terrain guarding, but the odd-k bound rests on a quasiconvex-programming reduction that is asserted, not proved. read the letter →

arxiv 2505.02373 v1 pith:RM4VPLFJ submitted 2025-05-05 cs.CG

Byeonguk Kang , Hwi Kim , Hee-Kap Ahn This is my paper · ORCID
classification cs.CG MSC 68U0568Q25
keywords terrainguardingpointguardslowesthorizontallinex-monotonepolygonalchainDavenport-Schinzelsequencesvisibilitybijectivecovercomputationalgeometry
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

The paper studies a basic camera-placement problem: given an x-monotone polygonal terrain with n vertices and k point guards that must lie on one horizontal line above the terrain, how low can that line be while every point of the terrain is visible from at least one guard? It gives exact algorithms for this Altitude Terrain Cover problem, with running time O($k^{2}$ λ_{k-1}(n) log n) for even k ≥ 2 and O($k^{2}$ λ_{k-2}(n) log n) for odd k ≥ 3, where λ_s(n) is the near-linear Davenport-Schinzel extremal function; for any fixed k these bounds are nearly linear in n. For the bijective variant, in which the terrain is partitioned into k subchains each assigned to its own guard, it gives an O(n)-time algorithm when the line is fixed and an O(kn)-time algorithm when the line is optimized. The interest is that these are exact worst-case bounds for a problem whose general terrain-guarding relatives are NP-hard; the one-dimensional structure of the chain is enough to make the optimal altitude and guard placements provably fast to compute.

What carries the argument

The machinery is a pair of monotone extremal functions f_i(h) and g_i(h) defined for a candidate altitude h. For the still-uncovered part of the terrain, f_i(h) records the extreme position from which the leftmost uncovered portion can be seen, and g_i(h) is the mirror for the rightmost uncovered portion; placing guards at these extreme positions dominates any other placement. With shortest path trees from the two endpoints, the functions become piecewise rational, and Davenport-Schinzel sequence bounds control how many times such rational upper envelopes can alternate, which is what makes the interval-shrinking scheme efficient. For the bijective variant the load-bearing mechanism is Lemma 18, which says some optimal partition has every subchain endpoint at a terrain vertex; that reduces an exponential search over partitions to a sweep over O(n) y-intervals per guard.

What would settle it

Take a two-guard bijective instance and compute, for every vertex split i, the value max{height of the lowest point of the half-plane intersection for the left subchain, same for the right subchain}; then also test non-vertex split points inside each edge. If any interior split gives a strictly smaller maximum than all vertex splits, Lemma 18 is false and the O(kn) altitude algorithm cannot be optimal; the same check on random small terrains would settle the structural claim.

Watch

Extended reading notes

Core claim

The paper's central claim is that both 'cover the whole terrain' and 'partition into guarded subchains' have polynomial exact algorithms with explicit near-linear bounds. Concretely, Theorem 2 states that for even k > 2 the optimal altitude line can be found in O($k^{2}$ λ_{k-1}(n) log n) time, and Theorem 3 states the odd case runs in O($k^{2}$ λ_{k-2}(n) log n) time; λ_s(n) denotes the maximum length of an (n,s)-Davenport-Schinzel sequence. Theorems 4 and 5 cover the bijective variant: with the line fixed, the minimum number of guards is found in O(n) time, and with the number of guards fixed the lowest line is found in O(kn) time. The paper further proves the k=2 ATC case in O(n log n) time and the k=1 case in O(n) time.

Load-bearing premise

The O(kn) bijective optimization rests on Lemma 18, the claim that some optimal solution cuts the terrain only at vertices; if the true optimum required a split strictly inside an edge, the vertex-only search would miss it.

Editorial extensions

If this is right

  • For any fixed k, the ATC running times are near-linear in n, so the lowest-line placement can be computed exactly on large terrains instead of by exponential search or heuristics.
  • The k=2 case runs in O(n log n) time, improving on the generic O(kn^2) parametric-search approach the paper identifies as the naive baseline.
  • In the bijective variant, a fixed line admits a linear-time greedy placement of the minimum number of guards, and optimizing the line costs O(kn), so the dependence on terrain size stays linear even as k grows.
  • For odd k the algorithm reduces the search to the lowest crossing of the two middle envelope functions, so once the interval I_⌊k/2⌋ is known the remaining work is O(kn) rather than another full sweep.

Reading between the lines

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

  • The vertex-cut lemma suggests a discretization principle: for guard-subchain bijections on x-monotone terrains, optimal boundaries may always be pushed to vertices. If that holds for other one-dimensional guard models, similar O(n)-per-guard sweeps could apply.
  • The dominance of extreme guards implies the optimal altitude is determined entirely by the middle pair of guards and the edges between them; this opens the possibility of a data-structure version where the terrain is preprocessed and the optimal line for any k is answered by a local middle-edge query.
  • The O(n) intervals of constant coverage status maintained for each guard suggest the natural lower-bound target for the bijective altitude problem: a terrain forcing Ω(n) distinct breaks per guard would show the O(kn) sweep cannot be improved by a simple interval-counting argument.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

Summary. The paper studies two terrain guarding problems in which guards are points on a horizontal line above an x-monotone terrain. In the Altitude Terrain Cover (ATC) problem, the goal is to place k guards on the lowest possible horizontal line so that every terrain point is visible from some guard. The authors claim an O(k^2 λ_{k-1}(n) log n)-time algorithm for even k ≥ 2 and an O(k^2 λ_{k-2}(n) log n)-time algorithm for odd k ≥ 3, where λ_s(n) is the maximum length of an (n,s)-Davenport-Schinzel sequence. In the Bijective Altitude Terrain Cover (BATC) problem, the terrain must be partitioned into k subchains, each paired with one guard; the authors claim an O(n)-time algorithm for minimizing the number of guards on a fixed line and an O(kn)-time algorithm for optimizing the line height when k is fixed. The ATC algorithms iteratively narrow a y-interval containing the optimal height using monotone envelope functions, and the BATC algorithms exploit structural properties of optimal vertex partitions.

Significance. If the claims are correct, the paper gives exact worst-case bounds for a natural terrain guarding optimization, improving on the parametric-search approach sketched in the introduction, and the linear-time BATC results are elegant. The paper has a coherent overall architecture: dominance lemmas, shortest-path-tree reductions for visibility, degree-control for rational envelopes, and a candidate-partition scheme for the bijective variant. The paper is a theoretical contribution with no experimental component, which is appropriate for this type of result. However, two load-bearing steps are not yet supported by the text: the quasiconvex-programming reduction for odd k in Theorem 3, and the structural Lemma 18 that justifies restricting BATC to vertex partitions. The even-k ATC bound also relies on an envelope-computation step in Lemma 16 whose oracle and induction invariant are not fully specified.

major comments (3)
  1. [3.3 (Theorem 3)] The reduction to quasiconvex programming is the load-bearing step for odd k, and it is not derived. The proof states that h* is found "using quasiconvex programming [ABE99]" and that "the lowest vertex of the upper envelopes" is computed in O(kn) time, but no quasiconvex objective function, no oracle, and no argument that [ABE99]'s hypotheses are satisfied by the rational envelopes from Lemma 14 are given. This matters because the envelopes can have combinatorial complexity O(λ_{k-2}(n)), which may be superlinear, so an O(kn)-time algorithm cannot materialize them and would need a prune-and-search oracle with a proof of exactness. In addition, f_m is defined as the leftmost point among the f(e,h), i.e. a pointwise minimum in the x-coordinate, so describing it as an "upper envelope" is at best misleading; the actual objective h ↦ x(f_m(h)) - x(g_m(h)) and its quasiconvexity properties should be stated explicitly. Without this derivation, Theorem 3's bound is unsupported.
  2. [Lemma 18 (Section 4)] Lemma 18 is load-bearing for the O(kn) BATC bound, because it restricts the search to partitions whose endpoints are vertices, but the proof as written does not establish the claim. After choosing w on v_j v_{j+1}, the proof argues from a point p in v_j w (which lies to the left of w) that the subchain T(p,w) is contained in T_i, although T_i begins at w; the indexing is inconsistent. Moreover, the presence of a blocking vertex v with x(v_{j+1}) < x(v) < x(u'_i) does not by itself imply that every point of T(p,w) is invisible from u'_i, so the claimed contradiction does not follow. Please provide a complete proof of the structural lemma, or a corrected statement; without it, the vertex-partition restriction and hence the O(kn) result are not justified.
  3. [Lemma 16 (Section 3.2)] Lemma 16's computation of I_i from I_{i-1} needs additional justification at the envelope step. The proof asserts that because any two rational functions in Π_{i,i-1} intersect at most 2i-1 times, the upper envelope of the family can be computed in O(k λ_{2i-1}(n) log n) time by [SA95]. This is only valid if the family of functions is fixed on the interval I and if exact comparisons of the rational functions can be performed within the stated time; the text does not specify the comparison oracle, and the family {f(e(i,h),h) : e not in U_{i-1}(h)} is defined through the h-dependent portions e(i,h), so its invariance on I is not immediate. Since every subsequent interval I_i and the final even-k bound depend on this step, the proof should spell out the induction invariant and the oracle.
minor comments (4)
  1. [Section 2 / notation] The symbol pq is used both for the segment between p and q and for the line through p and q; the two uses are visually indistinguishable in the submitted text. Please use different notation, for example an overline for the segment and a double-bar for the line.
  2. [Lemma 11 / Figure 5] In the proof of Lemma 11, the points q1 and q2 are referenced in the discussion of peak changes, but they are not labeled in Figure 5(b), which makes the argument harder to follow.
  3. [Lemma 8] The citation [SMN23] is used for computing the upper envelope in O(n) time. For arbitrary lines, upper envelopes usually require O(n log n) unless slopes are sorted; please state which precondition holds here or replace the citation.
  4. [Section 3.3] The phrase "lowest vertex of the upper envelopes" is not defined. If it is intended to mean the minimum h at which the two envelopes cross, that should be stated explicitly and connected to the equality x(f_m(h)) = x(g_m(h)).

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the ATC/BATC derivations are self-contained, with only a tangential self-citation.

full rationale

The paper's derivation chain is self-contained. The geometric quantities f(e,h), g(e,h), f_i(h), and g_i(h) are defined directly from terrain edges, visibility, and shortest-path trees, and the optimal altitude h* is characterized as the minimum h at which monotone functions cross, not defined in terms of the algorithm's own output. External citations are used for standard ingredients: shortest-path trees [GHL+86], linear-time fixed-line guard decisions [DFM+19], Davenport-Schinzel bounds [SA95], parametric search [Meg83], fixed-dimension LP [Meg84], and quasiconvex programming [ABE99]. None of these are self-citations. The only self-citation, [KCHA24], appears in related work as a watchtower variant and is not used in any proof; it is therefore not load-bearing. The odd-k proof compresses the quasiconvex-programming reduction to [ABE99] without explicitly deriving the quasiconvex function or oracle, which is an unverified technical gap and a correctness risk, but not circularity: it does not make the claimed time bound equivalent by construction to the paper's inputs. No fitted parameter is renamed as a prediction, and no target quantity is defined in terms of its own output. Under the hard rule that circularity must be exhibited by a specific equation or self-citation reduction, no such step exists here.

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

The paper introduces no new physical or mathematical entities and fits no parameters to data. Its main external assumptions are the fixed-line decision algorithm of Daescu et al., shortest path tree construction, Davenport-Schinzel envelope bounds, and the quasiconvex programming oracle of Amenta et al. These are standard and clearly cited. The structural lemmas, such as the endpoint-vertex partition property, are proved in the text, though briefly.

assumptions (5)
  • domain assumption A terrain is an x-monotone polygonal chain, and visibility is by straight segments that do not cross the terrain.
    Problem definition; all proofs rely on this monotonicity for Lemmas 4-5 and the greedy placement arguments.
  • domain assumption There is a linear-time algorithm to decide, for a fixed altitude h, whether the minimum number of guards on L(h) covers the terrain (Daescu et al. [DFM+19]).
    Used as a black-box decision oracle in binary search over h in Lemmas 9, 10, 11, 15, and 16.
  • standard math Shortest path trees of a simple polygon from a vertex can be built in linear time, and parent pointers characterize visibility (Guibas et al. [GHL+86]).
    Used in Lemmas 6-7 to compute f(e,h) and g(e,h) in O(1) time.
  • standard math The upper envelope of n univariate functions with at most s pairwise intersections has complexity O(lambda_s(n)) (Davenport-Schinzel theory [SA95]).
    Used to bound the complexity of f_i and g_i in Lemma 16 and to set the running times of the algorithms.
  • domain assumption Quasiconvex programming can find the lowest point on the upper envelope of monotone functions in linear time (Amenta, Bern, Eppstein [ABE99]).
    Used in Theorem 3 to locate the optimal height for odd k, without a fully detailed reduction in the text.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Guarding Terrains with Guards on a Line." pith.science (2026). https://pith.science/paper/RM4VPLFJ

@misc{pith2026250502373,
  author       = {Pith},
  title        = {Pith review of: Guarding Terrains with Guards on a Line},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RM4VPLFJ}},
  note         = {Machine review of arXiv:2505.02373}
}
abstract

Given an $x$-monotone polygonal chain $T$ with $n$ vertices, and an integer $k$, we consider the problem of finding the lowest horizontal line $L$ lying above $T$ with $k$ point guards lying on $L$, so that every point on the chain is \emph{visible} from some guard. A natural optimization is to minimize the $y$-coordinate of $L$. We present an algorithm for finding the optimal placements of $L$ and $k$ point guards for $T$ in $O(k^2\lambda_{k-1}(n)\log n)$ time for even numbers $k\ge 2$, and in $O(k^2\lambda_{k-2}(n)\log n)$ time for odd numbers $k \ge 3$, where $\lambda_{s}(n)$ is the length of the longest $(n,s)$-Davenport-Schinzel sequence. We also study a variant with an additional requirement that $T$ is partitioned into $k$ subchains, each subchain is paired with exactly one guard, and every point on a subchain is visible from its paired guard. When $L$ is fixed, we can place the minimum number of guards in $O(n)$ time. When the number $k$ of guards is fixed, we can find an optimal placement of $L$ with $k$ point guards lying on $L$ in $O(kn)$ time.

Figures

Figures reproduced from arXiv: 2505.02373 by the authors.

Figure 1
Figure 1. Cases for k = 2. (a) The optimal placement of L such that T can be covered by two guards lying on L. (b) The optimal placement of L such that T is partitioned into two subchains: one of them is visible from the red guard and the other is visible from the blue guard. 2 [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. (a) The gray region is the set of points visible from every point of e. g(e, h) (resp. f(e, h)) is the leftmost (resp. rightmost) point of L(h) in the region. (b) f(h) is the leftmost point among f(e, h) for all edges e of T. Lemma 3 Vis(u) ⊆ Vis(f(h)) for any point u ∈ L(h) with x(u) < x(f(h)), and Vis(w) ⊆ Vis(g(h)) for any point w ∈ L(h) with x(w) > x(g(h)). We need a few technical lemmas. The first lemma is from… view at source ↗
Figure 3
Figure 3. (a) Red dashed segments are edges of Sn. For any fixed h ∈ I0, (b) f(vv′ , h) = f(v, h) if x(πn(v)) < x(πn(v ′ )). (c) f(vv′ , h) = f(v ′ , h) if x(πn(v)) ⩾ x(πn(v ′ ). Lemma 7 Let vv′ be an edge of T with x(v) < x(v ′ ). For any h ∈ I0, f(vv′ , h) = f(v, h) if x(πn(v)) < x(πn(v ′ )), and f(vv′ , h) = f(v ′ , h) otherwise. Proof. Observe that either f(vv′ , h) = f(v, h) or f(vv′ , h) = f(v ′ , h) because T is x-mono… view at source ↗
Figures from the paper (7 more)
Figure 4
Figure 4. Figure 4: (a) Red and blue half-line represents f(e, h) and g(e, h) for an edge e of T, respectively. (b) We have W = ⟨w1, w2, w3, w4, w5⟩, and (y0, y′ 0 ] = y(w3), y(w4) [PITH_FULL_IMAGE:figures/full_fig_p008_4.png]
Figure 5
Figure 5. Figure 5: (a) e is an edge of T. f(h) = g(e, h). (b) vv′ is an edge of S1. We have that vv′ ∩ e is contained in the interior of e, q = f(h) ∩ vv′ , and peak(e, q) = {v, v′} for h = y(q). For arbitrary small ϵ > 0, peak(e, q1) = {v ′} for h = y(q) + ϵ, and peak(e, q2) = {v} for h…
Figure 6
Figure 6. Figure 6: Proof of Lemma 14. Lemma 16 For any integer i with 1 < i ⩽ k/2, we can compute Ii given Ii−1 in O(kλ2i−1(n) log n) time. Proof. We first compute the y-interval I such that Ii ⊆ I ⊆ Ii−1, and f(e, h) and g(e, h) for h ∈ I are in Πi,i−1 for any edge e of T with e ̸∈ Ui−1…
Figure 7
Figure 7. Figure 7: The ray emanating from v12 towards v8 intersects v3v4 at p1. The ray emanating from v8 towards v6 intersects v3v4 at p2. The ray emanating from v12 towards v10 intersects v8v9 at p3. Since πn(v6) = v8, x(p1) ⩽ x(p2). Since πn(πn(v6)) = πn(v10) and x(πn(v6) = v8) ⩽ x(v1…
Figure 8
Figure 8. Figure 8: (a) w(1, 8) = w(1, 9) because v8v9 has a negative slope and w(1, 8) lies above v8v9. (b) w(1, 9) = ∂R(1, 8) ∩ v8v9 because v8v9 has a negative slope and w(1, 8) lies below v8v9, where ∂R(1, 8) is the boundary of R(1, 8). Recall that our algorithm finds, for each guard …
Figure 9
Figure 9. Figure 9: The orange chain ∂E +(1, 8) is the boundary of E +(1, 8). The rightmost point of E +(1, 8) ∩ L(y(T)) is w. We have s1,1 = 5 because v5v6 is the leftmost edge of T such that w lies below v5v6. s1,2 = 7 because w(1, 6) = w(1, 7) and w(1, 7) ̸= w(1, 8). Let I1,1, . . . , …
Figure 10
Figure 10. Figure 10: (a) ∂E +(1, 11) is the boundary of E +(1, 11). ∂E +(7, 11) is the boundary of E +(7, 11). E +(s1,2, n) = E +(7, 11). (b) Computation of ∂P(I1,2) using E +(7, 11), where ∂P(I1,2) is the boundary of P(I1,2). By Lemma 21, we can compute all si,j ’s for guards ui and the …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references · 16 canonical work pages

  1. [1]

    Guarding a terrain by two watchtowers

    Pankaj K Agarwal, Sergey Bereg, Ovidiu Daescu, Haim Kaplan, Simeon Ntafos, Micha Sharir, and Binhai Zhu. Guarding a terrain by two watchtowers. Algorithmica , 58(2):352--390, 2010

    work page 2010

  2. [2]

    Optimal point placement for mesh smoothing

    Nina Amenta, Marshall Bern, and David Eppstein. Optimal point placement for mesh smoothing. Journal of Algorithms , 30(2):302--322, 1999

    work page 1999

  3. [3]

    On the planar two-watchtower problem

    Sergei Bespamyatnikh, Zhixiang Chen, Kanliang Wang, and Binhai Zhu. On the planar two-watchtower problem. In Computing and Combinatorics: 7th Annual International Conference (COCOON 2001) , pages 121--130, 2001

    work page 2001

  4. [4]

    Contiguous boundary guarding

    Ahmad Biniaz, Anil Maheshwari, Joseph SB Mitchell, Saeed Odak, Valentin Polishchuk, and Thomas Shermer. Contiguous boundary guarding. arXiv preprint arXiv:2412.15053 , 2024

    arXiv 2024

  5. [5]

    Optimal guarding of polygons and monotone chains

    Danny Z Chen, Vladimir Estivill-Castro, and Jorge Urrutia. Optimal guarding of polygons and monotone chains. In 7th Canadian Conference on Computational Geometry (CCCG 1995) , pages 133--138, 1995

    work page 1995

  6. [6]

    Visibility problems for polyhedral terrains

    Richard Cole and Micha Sharir. Visibility problems for polyhedral terrains. Journal of symbolic Computation , 7(1):11--30, 1989

    work page 1989

  7. [7]

    Altitude terrain guarding and guarding uni-monotone polygons

    Ovidiu Daescu, Stephan Friedrichs, Hemant Malik, Valentin Polishchuk, and Christiane Schmidt. Altitude terrain guarding and guarding uni-monotone polygons. Computational Geometry , 84:22--35, 2019

    work page 2019

  8. [8]

    Linear time algorithms for visibility and shortest path problems inside simple polygons

    Leonidas Guibas, John Hershberger, Daniel Leven, Micha Sharir, and Robert Tarjan. Linear time algorithms for visibility and shortest path problems inside simple polygons. In In 2nd annual symposium on computational geometry (SCG 1986) , pages 1--13, 1986

    work page 1986

Show all 17 references
  1. [9]

    Guarding points on a terrain by watchtowers

    Byeonguk Kang, Junhyeok Choi, Jeesun Han, and Hee-Kap Ahn. Guarding points on a terrain by watchtowers. In 36th Canadian Conference on Computational Geometry (CCCG 2024) , pages 41--47, 2024

    2024

  2. [10]

    Terrain guarding is NP -hard

    James King and Erik Krohn. Terrain guarding is NP -hard. SIAM Journal on Computing , 40(5):1316--1339, 2011

    2011

  3. [11]

    Parametric search: three new applications

    Naoki Katoh, Wencheng Wang, Yinfeng Xu, and Binhai Zhu. Parametric search: three new applications. Frontiers of Mathematics in China , 5:65--73, 2010

    2010

  4. [12]

    Applying parallel computation algorithms in the design of serial algorithms

    Nimrod Megiddo. Applying parallel computation algorithms in the design of serial algorithms. Journal of the ACM (JACM) , 30(4):852--865, 1983

    1983

  5. [13]

    Linear programming in linear time when the dimension is fixed

    Nimrod Megiddo. Linear programming in linear time when the dimension is fixed. Journal of the ACM (JACM) , 31(1):114--127, 1984

    1984

  6. [14]

    Guarding precise and imprecise polyhedral terrains with segments

    Bradley McCoy, Binhai Zhu, and Aakash Dutt. Guarding precise and imprecise polyhedral terrains with segments. In International Conference on Combinatorial Optimization and Applications , pages 323--336. Springer, 2023

    2023

  7. [15]

    Davenport-Schinzel Sequences and Their Geometric Applications

    Micha Sharir and Pankaj K Agarwal. Davenport-Schinzel Sequences and Their Geometric Applications . Cambridge University Press, 1995

    1995

  8. [16]

    Acrophobic guard watchtower problem

    Ritesh Seth, Anil Maheshwari, and Subhas C Nandy. Acrophobic guard watchtower problem. Computational Geometry , 109:101918, 2023

    2023

  9. [17]

    Guarding polyhedral terrain by k-watchtowers

    Nitesh Tripathi, Manjish Pal, Minati De, Gautam Das, and Subhas C Nandy. Guarding polyhedral terrain by k-watchtowers. In Frontiers in Algorithmics: 12th International Workshop (FAW 2018) , pages 112--125, 2018

    2018

Pith tools

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