Pith. sign in

REVIEW 3 major objections 4 minor 12 references

Simpler and Faster Contiguous Art Gallery

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

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

Pith's one-line read A greedy algorithm starting from one of O(n²) carefully chosen boundary points finds an optimal contiguous guard set in O(k n² log² n) time.

desk verdict A strong structural result with a load-bearing geometric lemma that is false as written; worth a careful referee. read the letter →

arxiv 2508.09734 v1 pith:4N7WWSTC submitted 2025-08-13 cs.CG

Sarita de Berg , Jacobus Conradi , Ivor van der Hoog , Frank Staals This is my paper · ORCID
classification cs.CG MSC 68U05
keywords contiguousartgallerysimplepolygonvisibilitycoresupporting-linearrangementgreedyalgorithmshortestpathscandidatesetcomputationalgeometry
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 gives a polynomial-time algorithm for the contiguous art gallery problem: place the fewest guards in a simple polygon so that each guard is assigned one contiguous boundary interval it can see, and the intervals cover the boundary. The authors prove that an optimal solution can always be found by a greedy procedure if it starts at one of O(n²) candidate boundary points, and they build a data structure that answers each greedy step in O(log² n). The result is an O(k n² log² n)-time, O(n²)-space algorithm, improving on the previous best O(k n⁵ log n) polynomial bound. If the structural theorem holds, the problem has a simple explanation: all hard choices collapse to intersections of supporting lines of polygon edges.

What carries the argument

The central objects are the visibility core P_E and the arrangement C_P of supporting lines of polygon edges. The visibility core of a set of boundary edges is the intersection of the halfplanes left of their directed supporting lines; a point guards a chain exactly when it lies in the core of the edges the chain crosses. The arrangement's vertices—intersections of two supporting lines—provide the O(n²) candidate guard positions, and the candidate start set U_P comes from maximal visible chains through the defining edges of these vertices. The good/bad guard split is the crucial dichotomy: a guard is good unless the open chain contains a polygon vertex, the guard is not an endpoint, the view

What would settle it

Take a simple polygon and a bad guard whose shortest path from v to u is a convex left-turning chain with three or more edges; compute the visibility core P_E of the boundary chain and intersect the supporting line of the last edge with it. Compare the maximal chain seen by the intersection point with the true visibility polygon of that point. If the point fails to see any part of [u,v] that the halfplane argument claims, then Lemma 4.9's reduction is false for that instance.

Watch

Extended reading notes

Core claim

The paper establishes that the contiguous art gallery problem can be solved in O(k n² log² n) time. Its central structural theorem shows that, for any optimal solution using more than one guard, there is an equal-size optimal solution in which at least one guard's interval starts at a point in a precomputed set U_P of O(n²) boundary points. From such a start, the greedy rule—take the farthest boundary point v such that some guard sees the whole interval [u, v], then repeat from v—produces an optimal solution. The paper additionally proves a query data structure: for any requested start u, the maximal guardable interval from u can be returned in O(log² n) time, with a witness guard. Together

Load-bearing premise

The load-bearing premise is Lemma 4.9: for a bad guard, the visibility core of the convex shortest-path chain is completely described by the halfplanes left of its first and last edges, so the middle edges never further restrict visibility. If a middle edge can cut the core, the data structure's bad-guard query may certify a chain that the returned guard does not actually see.

Editorial extensions

If this is right

  • If the structural theorem is correct, the optimum can be computed by running the greedy maximal-interval rule from every candidate start in U_P and keeping the best output; no backtracking or iterative restart is needed.
  • The running time is O(k n² log² n) using O(n²) space, a large asymptotic improvement over the previous O(k n⁵ log n) polynomial bound.
  • Every greedy run returns at most k+1 guards, and the run starting from the guaranteed candidate returns exactly k guards.
  • The query data structure returns a witness guard along with the maximal chain, so the algorithm outputs an explicit set of contiguous guards, not just a count.

Reading between the lines

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

  • The good/bad split may generalize to other boundary-coverage variants: whenever a single guard's visible region is described by a convex visibility core, arrangement vertices can serve as finite candidate sets, potentially yielding polynomial algorithms elsewhere.
  • If the bad-guard simplification in Lemma 4.9 is ever replaced by an exact visibility query, the rest of the pipeline—O(n²) candidate starts, the greedy proof, and the polylogarithmic query structure—should carry over unchanged.
  • One could try to shrink U_P further by keeping only arrangement vertices whose two defining edges are both intersected by the maximal chain, which would sharpen the O(n²) factor without changing the method.
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 proposes an O(k n^2 log^2 n)-time, O(n^2)-space algorithm for the contiguous art gallery problem. The approach is to show that there is an optimal solution containing a guard whose chain starts in an O(n^2)-size candidate set U_P, and to build a data structure that, for any start point u, returns the maximal chain [u,v] guardable by a single contiguous guard in O(log^2 n) time. The structural core is a classification of guards into "good" and "bad": good guards are replaced by vertices of the arrangement of edge-supporting lines, while bad guards are handled through a claim about the visibility core of the shortest path between u and v. The main theorem follows by running the greedy algorithm from every candidate start point.

Significance. If correct, this is a substantial improvement: the fastest previous algorithm runs in O(k n^5 log n) time, and the proposed solution is both simpler and faster. The paper has genuine strengths: it presents an explicit O(n^2) candidate set, uses standard shortest-path and ray-shooting primitives, and avoids fitted parameters or black-box quantifier elimination. The greedy optimality argument (Theorem 7.1) is a standard exchange argument and is plausible. However, the correctness of the whole construction depends on several geometric assertions that are not derived, the most serious being Lemma 4.9. Because the bad-guard branch of the query data structure (Lemma 6.8) rests on this lemma, the central claim is not currently established.

major comments (3)
  1. [Section 4.2, Lemma 4.9] The proof states: "the edges of Sv form a left-turning chain ... It follows that the visibility core of Sv is the intersection of the halfplanes left of ℓu and ℓv." This equality is false for arbitrary left-turning chains. For example, for the chain (0,0)->(10,0)->(10,10)->(0,10), the visibility core is {y≥0, x≤10, y≤10}, whereas the intersection of the first and last halfplanes is only {0≤y≤10}; the middle edge imposes an extra constraint. The proof supplies no argument that in the shortest-path context of a simple polygon, and with g seeing both u and v, the intermediate halfplanes are implied by the two extremes. This is load-bearing: Lemma 6.8's bad-guard case uses Lemma 4.9 to certify that the first/last intersection points g* of ℓu with PE lie in the true visibility core of Pv. If that certification fails, the query may output a maximal chain [u,v] that no single guard actually see
  2. [Section 5, Theorem 5.4] In the case where G contains only bad guards, the proof asserts: "As ∢(v,g,u)>π, any point that sees r and is left of the supporting line of vg must lie in the polygon Pg." No derivation is given, and this is not a direct consequence of the angle condition alone, since r is a reflex vertex outside [u,v]. The subsequent replacement of (g',[u',v']) by (g',[a,b]) also needs a formal argument that [a,b] is a single closed chain and that the replacement preserves a guarding set while making the guard good. Since Theorem 5.4 provides the existence of a start point u∈U_P in an optimal solution, this gap affects the correctness of the overall algorithm.
  3. [Section 6.1, Lemma 6.8] The binary search over edges e assumes monotonicity of the existence of a bad guard: if the shortest path from u to the maximal endpoint of e is not left-turning, then no v∈e admits a bad guard whose chain ends on e. This is asserted without proof. As the query point v moves along an edge, the combinatorial structure of the shortest path can change; it is not immediate that left-turning-ness of the path to the farther endpoint is necessary for all points on that edge. Since the correctness of the binary search depends on this monotonicity, this step needs a rigorous justification.
minor comments (4)
  1. [Throughout] There are several typos: "F unding" in the funding statement, "we we set" in the proof of Lemma 6.8, and "per definition" should be "by definition" in Lemma 4.9.
  2. [Definition 5.1] The phrase "the unique inclusion-wise maximal interval containing x" should be clarified: uniqueness is not immediate, since a guard c may see multiple maximal boundary intervals containing the same vertex x of a defining edge. If the definition relies on a tie-breaking rule, it should be stated.
  3. [Lemma 6.6] The proof says the bit string for neighboring vertices in the arrangement differs by at most two entries. This is true only if the walk between them crosses no other supporting line; the argument should specify that the walk follows edges of the arrangement, not arbitrary lines.
  4. [Theorem 7.1] The proof of the claim |G_u| ≤ k+1 for arbitrary u is compressed into a parenthetical. A short formal exchange argument would improve readability and make the O(k) bound for every greedy run explicit.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the algorithm's derivation is self-contained; the main risks are geometric correctness gaps, not circular reasoning.

full rationale

The paper's central claims—the O(n^2) candidate-start set U_P, the replacement of good guards by arrangement vertices, and the polylogarithmic query structure—are derived from independent geometric arguments about visibility cores, shortest paths, and arrangements of supporting lines. No fitted parameter is renamed as a prediction, and no central conclusion is defined in terms of itself. The only self-citation is [5] (Eades, van der Hoog, Löffler, Staals), used for the standard observation that a shortest path can be tested for left-turning in O(log n) time. That observation is a small subroutine inside Lemma 6.8, not the source of the main structural theorem, so it does not make the derivation circular. The most load-bearing geometric step, Lemma 4.9, asserts that the visibility core of a left-turning shortest path is the intersection of the halfplanes of only its first and last edges. As written, this 'it follows' is questionable for arbitrary left-turning chains, and if false would break the bad-guard branch of Lemma 6.8. However, that is a correctness risk, not a circular reduction: the asserted equality is a geometric fact that can be checked independently of the paper's outputs, and it is not introduced by fitting, renaming, or self-citation. Accordingly, the circularity score is low.

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

Pure combinatorial geometry paper: no free parameters, no fitted constants, no invented physical entities. The candidate sets U_P and G_P are finite sets derived from the arrangement, and 'good'/'bad' is a classification of guards, not an ad hoc entity. The axioms are standard computational geometry facts, all cited, plus the general-position assumption for the arrangement walk and the visibility-core characterization.

assumptions (4)
  • domain assumption P is a simple polygon in counterclockwise order, and the supporting-line arrangement C_P is in general position.
    General position is assumed in Lemma 6.6 ('If the vertices of P lie in general position, each vertex on this arrangement lies on exactly two supporting lines'); degenerate arrangements (parallel or coincident supporting lines) are not analyzed, while Theorem 7.1 states all simple polygons.
  • standard math Shortest-path queries and ray shooting in a simple polygon run in O(log n) time (Guibas-Hershberger [6]; Hershberger-Suri [8]).
    Invoked in Lemmas 6.3-6.5 and 6.8; these are published external data-structure results.
  • domain assumption Observation 4.8: if g sees u and v and angle(v,g,u) > pi, then the shortest path from u to v is a convex left-turning chain.
    Cited to [7] and used in Lemma 4.9 to analyze bad guards and in the convexity test of Lemma 6.8's binary search.
  • domain assumption Visibility-core equivalence (Observations 2.1-2.2): a guard sees a chain iff it lies left of the supporting lines of all edges intersecting the chain; a polygon is single-guardable iff its edge visibility core is nonempty.
    The foundational characterization used throughout the paper; argued inline rather than cited.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Simpler and Faster Contiguous Art Gallery." pith.science (2026). https://pith.science/paper/4N7WWSTC

@misc{pith2026250809734,
  author       = {Pith},
  title        = {Pith review of: Simpler and Faster Contiguous Art Gallery},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4N7WWSTC}},
  note         = {Machine review of arXiv:2508.09734}
}
read the original abstract

The contiguous art gallery problem was introduced at SoCG'25 in a merged paper that combined three simultaneous results, each achieving a polynomial-time algorithm for the problem. This problem is a variant of the classical art gallery problem, first introduced by Klee in 1973. In the contiguous art gallery problem, we are given a polygon P and asked to determine the minimum number of guards needed, where each guard is assigned a contiguous portion of the boundary of P that it can see, such that all assigned portions together cover the boundary of P. The classical art gallery problem is NP-hard and ER-complete, and the three independent works investigated whether this variant admits a polynomial-time solution. Each of these works indeed presented such a solution, with the fastest running in O(k n^5 log n) time, where n denotes the number of vertices of P and k is the size of a minimum guard set covering the boundary of P. We present a solution that is both considerably simpler and significantly faster, yielding a concise and almost entirely self-contained O(k n^2 log^2 n)-time algorithm.

Figures

Figures reproduced from arXiv: 2508.09734 by the authors.

Figure 1
Figure 1. Illustration of the visibility core PE (in green) of the set of edge E of P intersecting (u, v) (in black bold). Any vertex g ∗ of PE in Pg is a point that can see the entire dark grey polygon contiguous guard. Every vertex in CP is defined by two edges. We furthermore prove that, unless [u, v] contains no vertex of P, (u, v) contains at least one vertex of both edges defining c. 4.1 Replacing good guards. A contigu… view at source ↗
Figure 2
Figure 2. Illustration of proof of Lemma 4.9 with Pv in gray and the shortest path from vj+1 to u in red. of the last edge of Sv (the edge ending at u). Since g can see both u and v, the edges of Sv form a left-turning chain (Observation 4.8). It follows that the visibility core of Sv is the intersection of the halfplanes left of ℓu and ℓv. Observe that the polygon Pv defined by Sv and the chain [u, v] is well-defined (as g ̸… view at source ↗
Figure 3
Figure 3. Illustration of Theorem 5.4 which shows a bad contiguous guard (g, [u, v]). For a description of the vertices in the figure, we refer to the corresponding proof. We show the polygon Pg in gray. Proof. Since [u, v] is maximal, there exists a value ε ∗ > 0 such that for all ε ∈ (0, ε∗ ], the shortest path from g to the point v + ε on ∂P visits a reflex vertex x of ∂P. If x = v then v is a reflex vertex of P. Otherwise… view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Computing the inclusion-wise maximal area that can be seen by [PITH_FULL_IMAGE:figures/full_fig_p008_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 3 canonical work pages

  1. [5]

    Trajectory Visibility

    Patrick Eades, Ivor van der Hoog, Maarten L¨ offler, and Frank Staals. Trajectory Visibility. In Susanne Albers, editor, Scandinavian Symposium and Workshops on Algorithm Theory (SWAT) , volume 162 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 23:1–23:22, Dagstuhl, Germany, 2020. Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik.d...

    doi:10.4230/lipics.swat.2020.23 2020

  2. [1]

    The art gallery problem is ∃R-complete

    Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow. The art gallery problem is ∃R-complete. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , STOC 2018, page 65–73, New York, NY, USA, 2018. Association for Computing Machinery. doi:10.1145/3188745.3188868

    arXiv 2018

  3. [2]

    Ahmad Biniaz, Prosenjit Bose, Anil Maheshwari, Joseph S. B. Mitchell, Saeed Odak, Valentin Polishchuk, and Thomas C. Shermer. Contiguous boundary guarding. arXiv preprint arXiv:2412.15053 , 2024

    arXiv 2024

  4. [3]

    Ahmad Biniaz, Anil Maheshwari, Magnus Christian Ring Merrild, Joseph S. B. Mitchell, Saeed Odak, Valentin Polishchuk, Eliot W. Robson, Casper Moldrup Rysgaard, Jens Kristian Refsgaard Schou, Thomas Shermer, Jack Spalding-Jamieson, Rolf Svenning, and Da Wei Zheng. Polynomial-Time Algorithms for Contiguous Art Gallery and Related Problems. In Oswin Aichholz...

    2025

  5. [4]

    A combinatorial theorem in plane geometry.Journal of Combinatorial Theory, Series B , 18(1):39–41, 1975

    V´ aclav Chv´ atal. A combinatorial theorem in plane geometry.Journal of Combinatorial Theory, Series B , 18(1):39–41, 1975. Attributes the art gallery problem to Klee. doi:10.1016/0095-8956(75)90061-1

    doi:10.1016/0095-8956(75)90061-1 1975

  6. [6]

    Guibas and J

    L. Guibas and J. Hershberger. Optimal shortest path queries in a simple polygon. In Symposium on Computational Geometry (SoCG) , page 50–63, New York, NY, USA, 1987. Association for Computing Machinery. doi:10.1145/41958.41964

    arXiv 1987

  7. [7]

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

    L Guibas, J Hershberger, D Leven, M Sharir, and R Tarjan. Linear time algorithms for visibility and shortest path problems inside simple polygons. In Symposium on Computational Geometry (SoCG) , SCG ’86, page 1–13, New York, NY, USA, 1986. Association for Computing Machinery. doi:10.1145/10515.10516

    work page arXiv 1986

  8. [8]

    A pedestrian approach to ray shooting: shoot a ray, take a walk

    John Hershberger and Subhash Suri. A pedestrian approach to ray shooting: shoot a ray, take a walk. In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms , SODA ’93, page 54–63, USA, 1993. Society for Industrial and Applied Mathematics

    work page 1993

Show all 12 references
  1. [9]

    Lee and A

    D. Lee and A. Lin. Computational complexity of art gallery problems. IEEE Transactions on Information Theory, 32(2):276–282, 1986. doi:10.1109/TIT.1986.1057165

    1986

  2. [10]

    The contiguous art gallery problem is solvable in polynomial time

    Magnus Christian Ring Merrild, Casper Moldrup Rysgaard, Jens Kristian Refsgaard Schou, and Rolf Svenning. The contiguous art gallery problem is solvable in polynomial time. arXiv preprint arXiv:2412.13938 , 2024

    2024 arXiv

  3. [11]

    Robson, Jack Spalding-Jamieson, and Da Wei Zheng

    Eliot W. Robson, Jack Spalding-Jamieson, and Da Wei Zheng. The analytic arc cover problem and its applications to contiguous art gallery, polygon separation, and shape carving.arXiv preprint arXiv:2412.15567, 2024

    2024 arXiv

  4. [12]

    The Point-Boundary Art Gallery Problem Is ∃R-Hard

    Jack Stade. The Point-Boundary Art Gallery Problem Is ∃R-Hard. In Oswin Aichholzer and Haitao Wang, editors, 41st International Symposium on Computational Geometry (SoCG 2025) , volume 332 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 74:1–74:23, Dagstuh...

    2025 doi

Pith tools

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