Pith. sign in

REVIEW 4 major objections 4 minor 4 cited by

Contiguous Boundary Guarding

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

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

Pith's one-line read Requiring each guard to cover one contiguous boundary arc yields an exact polynomial-time algorithm.

desk verdict A genuinely new poly-time art-gallery variant; the exact algorithm is believable but rests on a long structural lemma that needs careful referee scrutiny. read the letter →

arxiv 2412.15053 v2 pith:CW5CVAY3 submitted 2024-12-19 cs.CG

Ahmad Biniaz , Anil Maheshwari , Joseph S. B. Mitchell , Saeed Odak , Valentin Polishchuk , Thomas Shermer This is my paper · ORCID
classification cs.CG MSC 68U05
keywords contiguousboundaryguardingsimplepolygonartgalleryproblemvisibilitygreedyalgorithmpolynomial-timeexactcombinatorialguardbound
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

Contiguous boundary guarding asks for the fewest guards inside a simple polygon such that the whole boundary is covered and each guard is assigned one contiguous arc of it. The paper's central result is that this constrained version can be solved exactly in polynomial time, even though the same guarding problem without the contiguity requirement is NP-hard. The argument combines a greedy sweep that is always within one guard of optimal with a structural lemma that produces a polynomial-size list of starting points from which the greedy sweep is exact. The paper also proves that any n-vertex polygon can be guarded with at most $\lfloor (n-2)/2 \rfloor$ guards and that this bound is tight.

What carries the argument

The load-bearing object is the finite candidate set $Q$: all polygon vertices, all points where an edge-extension or vertex-extension hits the boundary, all intersection points of two edge-extensions, and all intersection points of an edge-extension with a vertex-extension, where an extension is a segment from a reflex vertex along an incident edge or between two mutually visible reflex vertices, extended until it hits the boundary. $Q$ has $O(n^3)$ points, and Lemma 6 asserts that some optimal solution has a guard at a point of $Q$. From each $q \in Q$, the algorithm computes all possible first endpoints of the boundary arc a guard at $q$ could cover, producing the starting-point set $S$ of size $O(n^4)$; by Corollary 1 the greedy sweep from a double-covered starting point is exact. Lemma 6's proof is a contradiction argument: choose a lexicographically maximal optimal solution, show every guard has covering angle at least $\pi$ and lies on exactly one edge-extension, move consecutive guards so their assigned arcs meet in single points, and conclude that either a guard lands in $Q$ or the boundary cannot be fully covered.

What would settle it

Enumerate all optimal contiguous guardings for all simple polygons up to a small vertex count using exact arithmetic, and check whether every optimal set contains a guard from the paper's candidate set Q; a single polygon whose optimal sets all avoid Q would refute Lemma 6 and with it the exact algorithm.

Watch

Extended reading notes

Core claim

The paper establishes that the contiguous boundary guarding problem has a polynomial-time exact algorithm. The construction is explicit: build a polynomial-size candidate set Q of guard locations, derive from Q a polynomial-size set S of boundary points that are covered by two guards in some optimal solution, and run the greedy sweep from every point of S, keeping the smallest resulting guard set. The same proof yields the tight combinatorial bound $\lfloor (n-2)/2 \rfloor$ for every n-vertex simple polygon. The point of the result is contrast: without contiguity, guarding the boundary of a polygon is a hard optimization problem, so the single-interval assignment is what makes the problem tractable.

Load-bearing premise

The whole exact algorithm rests on Lemma 6, the claim that among all optimal guard sets there is one with a guard at a point of the finite candidate set Q; if some polygon had an optimal solution whose guards all avoid Q, the starting-point set S would miss the double-covered point and the greedy sweeps would not be guaranteed to find the optimum.

Editorial extensions

If this is right

  • The decision version of contiguous boundary guarding is in P, so optimal guard counts can be computed exactly rather than approximated.
  • A greedy sweep from an arbitrary boundary point returns a guard set of size at most $\mathrm{OPT}+1$, and it is exactly $\mathrm{OPT}$ whenever the starting point is covered by two guards in some optimal solution.
  • Every simple polygon with n vertices admits a contiguous boundary guarding with at most $\lfloor (n-2)/2 \rfloor$ guards, and some polygons require exactly that many.
  • The exact algorithm runs in $O(n^6 \log n)$ time, and the paper notes that this bound can likely be improved by using faster visibility-region updates.

Reading between the lines

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

  • Beyond the paper: the candidate-set construction is built entirely from single-arc visibility, so a natural testable conjecture is that the same approach extends to guards allowed a fixed number k of boundary intervals, with Q growing polynomially in n for each fixed k.
  • Beyond the paper: the contrast with the hard ordinary boundary-guarding problem suggests that the number of boundary components one guard may cover is the main source of hardness; if so, allowing k components should interpolate between polynomial and hard as k grows.
  • Beyond the paper: the OPT+1 greedy sweep, which is fast from a single start, could serve as a practical near-optimal rule for camera systems whose field of view is fixed and cannot rotate, with the exact algorithm available as a certifying check for small instances.
  • Beyond the paper: the structural proof is written for simple polygons, and it is an open question whether polygons with holes preserve Lemma 6; holes introduce additional reflex chains that the single-extension movement argument does not directly handle.
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

4 major / 4 minor

Summary. The paper studies the contiguous boundary guarding problem, in which guards must be placed in a simple polygon so that each guard is assigned a contiguous portion of the polygon boundary. The authors prove a tight combinatorial bound of floor((n-2)/2) guards for n-vertex polygons, give a simple greedy algorithm that uses at most OPT+1 guards, and present a polynomial-time exact algorithm. The exact algorithm works by constructing a polynomial-size candidate guard set Q and a set S of boundary starting points, then running the greedy algorithm from each starting point in S. Correctness of the exact algorithm rests on Lemma 6, which asserts that some optimal solution has a guard at a point of Q; the proof of Lemma 6 occupies most of Section 6 and is a long contradiction argument involving lexicographically maximal optimal solutions and continuous movements of guards along edge-extensions.

Significance. If correct, the main theorem is a significant result: the contiguous boundary guarding problem appears to be the first nontrivial boundary guarding variant that is solvable exactly in polynomial time, in contrast to standard point-guard or boundary-guard problems that are NP-hard and even ∃R-complete. The tight combinatorial bound is clean, and the OPT+1 greedy algorithm is simple and elegant. The candidate-set approach is appealing and could be reusable. The paper does not include code or machine-checked proofs, but the arguments are deductive and the external dependencies (visibility polygon computation, the cited lemma from Ghosh) are standard. The main weakness is that the proof of Lemma 6 is lengthy and partly compressed; several load-bearing geometric claims are asserted without full justification. No concrete error was found, but the proof needs substantial elaboration before the paper can be accepted.

major comments (4)
  1. [Section 6, first paragraph after the overview] The choice of Γ* as a maximal element of G with respect to the lexicographic order on angle sequences is not justified. The set G of optimal guard sets with maximal coverages is not obviously compact, and the text does not prove that a maximal element of this order exists. Since every subsequent argument in Section 6 is about Γ*, the proof of Lemma 6 depends on this existence. The authors should add a compactness or continuity argument, or explicitly construct Γ*, before the contradiction proof can be considered complete.
  2. [Section 6, paragraph starting 'By Lemma 12 for every gi ∈ Γ* ...'] The movement argument for constructing Γ is stated too tersely. In particular, the claims that during the movement 'gi cannot reach e(gi) or the boundary of P', 'gi cannot lie on a new edge-extension or vertex-extension', and 'the angle at w(gi) remains at least π because both bounding reflex vertices remain on the same side of the extension of e(gi)' are all asserted without proof. What is needed is a demonstration that the movement can always be continued until the desired intersection ∂(gi) ∩ ∂(gi+1) becomes a point, and that during this movement no point of the boundary that was previously covered becomes uncovered. As written, these steps are not checkable in detail, and they are load-bearing for the construction of Γ.
  3. [Section 6, Case 2 (OPT ≥ 3), Figure 14 and surrounding text] The inclusions 'The coverage ∂(gi+1) of gi+1 also lies in Ki because its first endpoint is xi and its last endpoint cannot go beyond ri' and 'This implies that Ki+1 is a subset of Ki' are not justified. These inclusions are essential for concluding that gm lies in K1 and hence that z'1 cannot be covered, which yields the final contradiction. The authors should provide a rigorous geometric argument for both inclusions, or restructure the proof to avoid them. As it stands, this part of the proof is too compressed to verify.
  4. [Section 3, Lemma 3] The proof of Lemma 3, that the covering region C(P,δ) of a polygonal path is a simple polygon, is a sketch rather than a complete proof. In the case where q∉Cp and p∉Cq, the text asserts that a boundary ray of Cp and a boundary ray of Cq intersect at a point c, but it does not handle degenerate configurations in which the rays are parallel or collinear, and the claim that c is in C is not fully proved. Since Lemma 3 underlies the polynomial-time computation of covering regions used by the greedy algorithm, its proof should be completed or the lemma should be stated as a direct consequence of the cited results [24,25] with a precise reference.
minor comments (4)
  1. [Section 2, lower bound construction] The sentence 'The chains are placed close to each other such that the midpoints of no three consecutive edges on a chain are visible from the same point in the polygon' is ambiguous; it should specify which points are 'consecutive midpoints' and clarify how the placement achieves the claimed visibility property.
  2. [Section 4, proof of Theorem 2] In the first case of the proof, the sentence 'By our choice of m and pm−1, the point p∗1 appears on or after pm−2, because otherwise p′1 would be in ∂(pm−2,pm−1)' is difficult to follow and should be expanded or rephrased for clarity.
  3. [Section 5, definition of F(q)] The statement that F(q) consists of intersections of ∂ with rays from q through reflex vertices relies on the maximality of ∂(g), which is assumed without loss of generality. It would help to state explicitly that maximality is assumed in the optimal solution under consideration and that this assumption is preserved by the construction of Q.
  4. [Section 6, Figures 13 and 14] The notation in the OPT=2 and OPT≥3 cases, such as w1, w2, A_i, B_i, and K_i, is introduced in the text but would be easier to follow if the figures were referenced more explicitly and if the definitions were repeated in the captions.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the paper's derivations are self-contained proofs with independent cited background lemmas.

full rationale

The paper is a pure deductive computational-geometry result. The greedy algorithm (Theorem 2) is proven from the definition of contiguous coverage and the covering-region lemmas, which are proved in the paper itself; the external references [24] and [25] for the covering-region ideas are not load-bearing because Lemmas 2 and 3 are each given full proofs in Section 3. The exact algorithm's correctness rests on Lemma 6, which is proved by a lengthy contradiction argument in Section 6 and is not derived by fitting or by renaming any known result. The candidate set Q is constructed from edge-extensions and vertex-extensions, and the proof of Lemma 6 does not assume the desired conclusion; it argues that a maximal optimal solution without a guard in Q leads to impossibility. The paper explicitly notes that the structural lemma is not true for every optimal solution (Section 5, Figure 7), which further confirms that the lemma is a genuine mathematical claim rather than a definitional tautology. There is no fitting of parameters, no prediction derived from fitted inputs, and no load-bearing self-citation: the only self-references in the reference list are to standard prior work by some of the authors (e.g., [10] for a diagonal partition fact), used as background rather than as the source of the main theorem. The tight bound in Theorem 1 is proved constructively from a triangulation dual argument and matched by an explicit lower-bound polygon, so it is not circular either. Overall the derivation chain is self-contained against the stated definitions, and no circular step is identifiable.

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

The paper introduces no fitted parameters and no new physical or mathematical entities. The sets Q, F(q), and S are finite candidate sets constructed from the input polygon and are not additional assumptions; they are outputs of the algorithm's search space. The axioms listed here are the background facts the proof relies on.

assumptions (4)
  • domain assumption Simple polygon without holes; guards may lie anywhere in the polygon and cover a connected boundary chain.
    Problem definition in Section 1.3. Changing to polygons with holes, vertex guards, or disconnected coverage would invalidate the results.
  • standard math Triangulation of an n-vertex simple polygon has a dual tree with n-2 nodes and maximum degree 3.
    Used in Lemma 1 and Theorem 1 to locate vertices covering consecutive edges.
  • standard math The covering region C(P,delta) of a boundary chain is a simple polygon and can be computed as the intersection of visibility polygons (Lemma 3).
    The paper's proof is a sketch and refers to Ghosh [24,25]; the greedy algorithm and Lemma 4 depend on this.
  • domain assumption A lexicographically maximal angle sequence among optimal guard sets exists, so the configuration Gamma* in Lemma 6 is well-defined.
    The proof in Section 6 chooses a maximal element of an infinite set without an explicit compactness argument; this is plausible since guards lie in a compact polygon.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Contiguous Boundary Guarding." pith.science (2026). https://pith.science/paper/CW5CVAY3

@misc{pith2026241215053,
  author       = {Pith},
  title        = {Pith review of: Contiguous Boundary Guarding},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CW5CVAY3}},
  note         = {Machine review of arXiv:2412.15053}
}
abstract

We study the problem of guarding the boundary of a simple polygon with a minimum number of guards such that each guard covers a contiguous portion of the boundary. First, we present a simple greedy algorithm for this problem that returns a guard set of size at most OPT + 1, where OPT is the number of guards in an optimal solution. Then, we present a polynomial-time exact algorithm. While the algorithm is not complicated, its correctness proof is rather involved. This result is interesting in the sense that guarding problems are typically NP-hard and, in particular, it is NP-hard to minimize the number of guards to see the boundary of a simple polygon, without the contiguous boundary guarding constraint. From the combinatorial point of view, we show that any $n$-vertex polygon can be guarded by at most $\lfloor \frac{n-2}{2}\rfloor$ guards. This bound is tight because there are polygons that require this many guards.

Figures

Figures reproduced from arXiv: 2412.15053 by the authors.

Figure 1
Figure 1. Illustration of the proof of Lemma 1. • Both p ′ and q ′ have degree 3. This case is depicted in [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Illustration of the lower bound ⌊ n−2 2 ⌋ guards. The polygonal arcs around the boundary are maximal chains that can each be guarded by a single guard. 3 Preliminaries for the Algorithms For two points p and q in the plane, we denote by pq the straight line segment between p and q. A ray from p toward q, denoted −→pq, is the half-line that starts from p and passes through q. A wedge is a region of the plane that is … view at source ↗
Figure 3
Figure 3. The boundary of the polygon is assumed to be directed counter-clockwise. [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figures from the paper (11 more)
Figure 4
Figure 4. Figure 4: Illustration of the proof of Theorem 2. (a) [PITH_FULL_IMAGE:figures/full_fig_p009_4.png]
Figure 5
Figure 5. Figure 5: (a). Now assume that w(g) = 2π. Then the two boundary rays of w(g) are identical. Moreover, they go through at least one reflex vertex because P is not star-shaped and g does not cover the entire ∂. This is depicted in [PITH_FULL_IMAGE:figures/full_fig_p010_5.png]
Figure 6
Figure 6. Figure 6: Edge-extensions are in red and vertex-extensions are in blue. The points in [PITH_FULL_IMAGE:figures/full_fig_p011_6.png]
Figure 7
Figure 7. Figure 7: An optimal solution, with two guards, none of which is in [PITH_FULL_IMAGE:figures/full_fig_p012_7.png]
Figure 8
Figure 8. Figure 8: Illustration of the proof of Lemma 7. g ∂(g) [PITH_FULL_IMAGE:figures/full_fig_p014_8.png]
Figure 9
Figure 9. Figure 9: Illustration of the proof of Lemma 8. Lemma 9. No guard g ∈ Γ ∗ lies on a vertex-extension. Proof. If g ∈ ∂, then g cannot be on a vertex-extension because otherwise, it would be in Q, a contradiction. If g /∈ ∂, then g is in the interior of P. In this case, g is on an…
Figure 10
Figure 10. Figure 10: Illustration of the proof of Lemma 10. Let α be the angle between B and C that lies inside w(g). If α is at most π, then by moving g on C either g reaches a vertex-extension, or another edge-extension, or an endpoint of e(g). This movement does not decrease ∂(g) becau…
Figure 11
Figure 11. Figure 11: Illustration of (a) the proof of Lemma 11, and (b) the statement of Lemma 12. [PITH_FULL_IMAGE:figures/full_fig_p016_11.png]
Figure 12
Figure 12. Figure 12: Illustration of the movement of g along the extension of e(g) or on e(g). By Lemma 12 for every gi ∈ Γ ∗ we have e(gi) ∈ w(gi)\α(gi). Assume that g /∈ e(gi). Consider moving gi along the extension of e(gi); see [PITH_FULL_IMAGE:figures/full_fig_p016_12.png]
Figure 13
Figure 13. Figure 13: Illustration of the proof for the case OPT = 2. [PITH_FULL_IMAGE:figures/full_fig_p017_13.png]
Figure 14
Figure 14. Figure 14: Illustration of the proof for the case OPT [PITH_FULL_IMAGE:figures/full_fig_p018_14.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 4 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. The Contiguous Art Gallery Problem is in {\Theta}(n log n)

    cs.CG 2025-11 unverdicted novelty 8.0 of 10

    The Contiguous Art Gallery problem is solved in Θ(n log n) time in the real RAM model, improving the prior O(k n^5 log n) upper bound and proving an Ω(n log n) lower bound.

  2. The Contiguous Art Gallery Problem is Solvable in Polynomial Time

    cs.CG 2024-12 conditional novelty 8.0 of 10

    The contiguous art gallery problem for simple polygons is solvable in O(k* n^5 log n) arithmetic operations, placing the problem in P.

  3. Simpler and Faster Contiguous Art Gallery

    cs.CG 2025-08 conditional novelty 7.0 of 10

    The contiguous art gallery problem is solvable in O(k n^2 log^2 n) time using O(n^2) candidate greedy start points and an O(log^2 n)-time farthest-visible-chain query.

  4. Guarding Terrains with Guards on a Line

    cs.CG 2025-05 conditional novelty 6.0 of 10

    For a terrain with n vertices, the paper gives an O(k^2 lambda_{k-1}(n) log n)-time algorithm for placing k guards on a lowest line above the terrain (even k), an analogous O(k^2 lambda_{k-2}(n) log n) bound for odd k...

Reference graph

Works this paper leans on

55 extracted references · 31 canonical work pages · cited by 4 Pith papers

  1. [1]

    The art gallery problem is ∃R-complete

    Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow. The art gallery problem is ∃R-complete. J. ACM, 69(1):4:1–4:70, 2022. Also in STOC’18. doi:10.1145/3486220. 18

    doi:10.1145/3486220 2022

  2. [2]

    Partitioning a Polygon Into Small Pieces

    Mikkel Abrahamsen and Nichlas Langhoff Rasmussen. Partitioning a polygon into small pieces. CoRR, abs/2211.01359, 2022. To appear in SODA’25. doi:10.48550/ARXIV.2211.01359

    work page Pith review arXiv doi:10.48550/arxiv.2211.01359 2022

  3. [3]

    The art gallery theorem: its variations, applications and algorithmic aspects

    Alok Aggarwal. The art gallery theorem: its variations, applications and algorithmic aspects . PhD thesis, The Johns Hopkins University, 1984

    work page 1984

  4. [4]

    Reymond Akpanya, Bastien Rivier, and Frederick B. Stock. Open problems CCCG 2024. In Proceedings of the 36th Canadian Conference on Computational Geometry , pages 167–170, 2024

    work page 2024

  5. [5]

    Terrain-like graphs: PTASs for guarding weakly-visible polygons and terrains

    Stav Ashur, Omrit Filtser, Matthew J Katz, and Rachel Saban. Terrain-like graphs: PTASs for guarding weakly-visible polygons and terrains. Computational Geometry, 101:101832, 2022. doi:10.1016/J.COMGEO.2021.101832

    work page arXiv 2022

  6. [6]

    Toussaint

    David Avis and Godfried T. Toussaint. An optimal algorithm for determining the visibility of a polygon from an edge. IEEE Trans. Computers , 30(12):910–914, 1981. doi:10.1109/TC. 1981.1675729

    arXiv 1981

  7. [7]

    Ivan J. Balaban. An optimal algorithm for finding segments intersections. In Proceedings of the 11th Annual Symposium on Computational Geometry (SCG) , pages 211–219. ACM, 1995. doi:10.1145/220279.220302

    arXiv 1995

  8. [8]

    Ntafos, and Junqiang Zhou

    Lichen Bao, Sergey Bereg, Ovidiu Daescu, Simeon C. Ntafos, and Junqiang Zhou. On some city guarding problems. In Proceedings of the 14th Annual International Conference on Computing and Combinatorics (COCOON) , pages 600–610. Springer, 2008

    work page

Show all 55 references
  1. [9]

    Approximability of guarding weak visibility polygons

    Pritam Bhattacharya, Subir Kumar Ghosh, and Bodhayan Roy. Approximability of guarding weak visibility polygons. Discrete Applied Mathematics , 228:109–129, 2017. doi:10.1016/J. DAM.2016.12.015

    2017 doi

  2. [10]

    Art galleries and mobile guards: Revisiting O’rourke’s proof

    Ahmad Biniaz. Art galleries and mobile guards: Revisiting O’rourke’s proof. In Proceedings of the 32nd Annual European Symposium on Algorithms (ESA) , volume 308 of LIPIcs, pages 27:1–27:4, 2024. doi:10.4230/LIPICS.ESA.2024.27

    2024 doi

  3. [11]

    City guarding with cameras of bounded field of view

    Ahmad Biniaz and Mohammad Hashemi. City guarding with cameras of bounded field of view. In Proceedings of the 35th Canadian Conference on Computational Geometry (CCCG) , pages 71–76, 2023

    2023

  4. [12]

    An approximation algorithm for the art gallery problem

    ´Edouard Bonnet and Tillmann Miltzow. An approximation algorithm for the art gallery problem. In 33rd International Symposium on Computational Geometry (SoCG) , volume 77 of LIPIcs, pages 20:1–20:15, 2017. doi:10.4230/LIPICS.SOCG.2017.20

    2017 doi

  5. [13]

    An optimal algorithm for intersecting line seg- ments in the plane

    Bernard Chazelle and Herbert Edelsbrunner. An optimal algorithm for intersecting line seg- ments in the plane. J. ACM, 39(1):1–54, 1992. doi:10.1145/147508.147511

    1992

  6. [14]

    Chen, Vladimir Estivill-Castro, and Jorge Urrutia

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

    1995

  7. [15]

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

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

    1975

  8. [16]

    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. doi:10.1016/J.COMGEO.2019.07.004

    2019 doi

  9. [17]

    New bounds on guarding problems for orthogonal polygons in the plane using vertex guards with halfplane vision

    Ovidiu Daescu and Hemant Malik. New bounds on guarding problems for orthogonal polygons in the plane using vertex guards with halfplane vision. Theor. Comput. Sci. , 882:63–76, 2021. doi:10.1016/J.TCS.2021.06.012

    2021 doi

  10. [18]

    van Kreveld, and Mark H

    Mark de Berg, Otfried Cheong, Marc J. van Kreveld, and Mark H. Overmars. Computational geometry: algorithms and applications, 3rd Edition . Springer, 2008

    2008

  11. [19]

    Demaine, and Sanjay E

    Ajay Deshpande, Taejung Kim, Erik D. Demaine, and Sanjay E. Sarma. A pseudopolynomial time O(log n)-approximation algorithm for art gallery problems. In Proceedings of the 10th International Workshop on Algorithms and Data Structures (WADS) , volume 4619, pages 163–174, 2007. ...

    2007 doi

  12. [20]

    Guarding galleries and terrains

    Alon Efrat and Sariel Har-Peled. Guarding galleries and terrains. Inf. Process. Lett. , 100(6):238–245, 2006. doi:10.1016/J.IPL.2006.05.014

    2006 doi

  13. [21]

    Eidenbenz, Christoph Stamm, and Peter Widmayer

    Stephan J. Eidenbenz, Christoph Stamm, and Peter Widmayer. Inapproximability re- sults for guarding polygons and terrains. Algorithmica, 31(1):79–113, 2001. doi:10.1007/ S00453-001-0040-8

    2001

  14. [22]

    ElGindy and David Avis

    Hossam A. ElGindy and David Avis. A linear algorithm for computing the visibility polygon from a point. J. Algorithms, 2(2):186–197, 1981. doi:10.1016/0196-6774(81)90019-5

    1981 doi

  15. [23]

    A short proof of chv´ atal’s watchman theorem

    Steve Fisk. A short proof of chv´ atal’s watchman theorem. Journal of Combinatorial Theory, Series B , 24(3):374, 1978. doi:10.1016/0095-8956(78)90059-X

    1978 doi

  16. [24]

    Computing the visibility polygon from a convex set and related problems

    Subir Kumar Ghosh. Computing the visibility polygon from a convex set and related problems. J. Algorithms, 12(1):75–95, 1991. doi:10.1016/0196-6774(91)90024-S

    1991 doi

  17. [25]

    Corrigendum: A note on computing the visibility polygon from a convex chain

    Subir Kumar Ghosh. Corrigendum: A note on computing the visibility polygon from a convex chain. J. Algorithms, 21(3):657–662, 1996. doi:10.1006/JAGM.1996.0064

    1996

  18. [26]

    Approximation algorithms for art gallery problems in polygons

    Subir Kumar Ghosh. Approximation algorithms for art gallery problems in polygons. Discret. Appl. Math., 158(6):718–722, 2010. Also in Canad. Information Processing Soc. Congress 1987. doi:10.1016/J.DAM.2009.12.004

    2010 doi

  19. [27]

    Krohn, and Kasturi R

    Matt Gibson, Gaurav Kanade, Erik A. Krohn, and Kasturi R. Varadarajan. Guarding terrains via local search. J. Comput. Geom. , 5(1):168–178, 2014. doi:10.20382/JOCG.V5I1A9

    2014 doi

  20. [28]

    Traditional galleries require fewer watchmen

    Jeff Kahn, Maria Klawe, and Daniel Kleitman. Traditional galleries require fewer watchmen. SIAM Journal on Algebraic Discrete Methods , 4(2):194–206, 1983

    1983

  21. [29]

    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 Proceedings of the 36th Canadian Conference on Computational Geometry, pages 41–47, 2024

    2024

  22. [30]

    Katz and Gabriel S

    Matthew J. Katz and Gabriel S. Roisman. On guarding the vertices of rectilinear domains. Comput. Geom., 39(3):219–228, 2008. doi:10.1016/J.COMGEO.2007.02.002. 20

    2008 doi

  23. [31]

    Kirkpatrick

    James King and David G. Kirkpatrick. Improved approximation for guarding simple gal- leries from the perimeter. Discret. Comput. Geom. , 46(2):252–269, 2011. doi:10.1007/ S00454-011-9352-X

    2011

  24. [32]

    Terrain guarding is NP-hard

    James King and Erik Krohn. Terrain guarding is NP-hard. SIAM J. Comput., 40(5):1316–1339,

  25. [33]

    Krohn and Bengt J Nilsson

    Erik A. Krohn and Bengt J Nilsson. Approximate guarding of monotone and rectilinear polygons. Algorithmica, 66:564–594, 2013. doi:10.1007/S00453-012-9653-3

    2013 doi

  26. [34]

    D. T. Lee. Visibility of a simple polygon. Comput. Vis. Graph. Image Process., 22(2):207–221,

  27. [35]

    D. T. Lee and Arthur K. Lin. Computational complexity of art gallery problems. IEEE Trans. Inf. Theory, 32(2):276–282, 1986. doi:10.1109/TIT.1986.1057165

    1986

  28. [36]

    D. T. Lee and Franco P. Preparata. An optimal algorithm for finding the kernel of a polygon. J. ACM, 26(3):415–421, 1979. doi:10.1145/322139.322142

    1979

  29. [37]

    Decomposing polygonal regions into convex quadrilaterals

    Anna Lubiw. Decomposing polygonal regions into convex quadrilaterals. In Proceedings of the first annual symposium on Computational geometry , pages 97–106, 1985. doi:10.1145/ 323233.323247

    1985

  30. [38]

    Covering orthogonal polygons with star polygons: The perfect graph approach

    Rajeev Motwani, Arvind Raghunathan, and Huzur Saran. Covering orthogonal polygons with star polygons: The perfect graph approach. J. Comput. Syst. Sci. , 40(1):19–48, 1990. Also in SCG’88. doi:10.1016/0022-0000(90)90017-F

    1990 doi

  31. [39]

    Galleries need fewer mobile guards: A variation on Chv´ atal’s theorem

    Joseph O’Rourke. Galleries need fewer mobile guards: A variation on Chv´ atal’s theorem. Geometriae Dedicata, 14:273–283, 1983

    1983

  32. [40]

    Art Gallery Theorems and Algorithms

    Joseph O’Rourke. Art Gallery Theorems and Algorithms . Oxford University Press, 1987

    1987

  33. [41]

    Shermer, and Ileana Streinu

    Joseph O’Rourke, Thomas C. Shermer, and Ileana Streinu. Illuminating convex polygons with vertex floodlight. In Proceedings of the 7th Canadian Conference on Computational Geometry (CCCG), pages 151–156, 1995

    1995

  34. [42]

    Some NP-hard polygon decomposition problems

    Joseph O’Rourke and Kenneth Supowit. Some NP-hard polygon decomposition problems. IEEE Transactions on Information Theory , 29(2):181–190, 1983. doi:10.1109/TIT.1983. 1056648

    1983 doi

  35. [43]

    Preparata and Michael Ian Shamos

    Franco P. Preparata and Michael Ian Shamos. Computational Geometry - An Intro- duction. Texts and Monographs in Computer Science. Springer, 1985. doi:10.1007/ 978-1-4612-1098-6

    1985

  36. [44]

    Toussaint

    J¨ org-R¨ udiger Sack and Godfried T. Toussaint. Guard placement in rectilinear polygons. In Machine Intelligence and Pattern Recognition , volume 6, pages 153–175. Elsevier, 1988

    1988

  37. [45]

    Two NP-hard art-gallery problems for ortho- polygons

    Dietmar Schuchardt and Hans-Dietrich Hecker. Two NP-hard art-gallery problems for ortho- polygons. Math. Log. Q. , 41:261–267, 1995. doi:10.1002/MALQ.19950410212

    1995 doi

  38. [46]

    Recent results in art galleries (geometry)

    Thomas C Shermer. Recent results in art galleries (geometry). Proceedings of the IEEE , 80(9):1384–1399, 1992. doi:10.1109/5.163407

    1992 doi

  39. [47]

    The point-boundary art gallery problem is ∃R-hard

    Jack Stade. The point-boundary art gallery problem is ∃R-hard. arXiv:2210.12817, 2023. 21

    2023 arXiv

  40. [48]

    Art gallery problem with guards whose range of vision is 180

    Csaba D T´ oth. Art gallery problem with guards whose range of vision is 180. Computational Geometry, 17(3-4):121–134, 2000. doi:10.1016/S0925-7721(00)00023-7

    doi

  41. [49]

    Art galleries with guards of uniform range of vision.Computational Geometry, 21(3):185–192, 2002

    Csaba D T´ oth. Art galleries with guards of uniform range of vision.Computational Geometry, 21(3):185–192, 2002. doi:10.1016/S0925-7721(01)00024-4

    2002 doi

  42. [50]

    Csaba D. T´ oth. Illumination of polygons by 45°-floodlights. Discret. Math., 265(1-3):251–260,

  43. [51]

    Art gallery and illumination problems

    Jorge Urrutia. Art gallery and illumination problems. In Handbook of computational geometry, pages 973–1027. Elsevier, 2000

    2000

  44. [52]

    Polygon decomposition and the orthogonal art gallery prob- lem

    Chris Worman and J Mark Keil. Polygon decomposition and the orthogonal art gallery prob- lem. International Journal of Computational Geometry & Applications , 17(02):105–138, 2007. doi:10.1142/S0218195907002264. 22

    2007 doi

  45. [1983]

    doi:10.1016/0734-189X(83)90065-8

    doi

  46. [2003]

    doi:10.1016/S0012-365X(02)00583-6

    doi

  47. [2011]

    doi:10.1137/100791506

    Also in SODA’10. doi:10.1137/100791506

    doi

Pith tools

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