Pith. sign in

REVIEW 3 major objections 5 minor 3 cited by

The Contiguous Art Gallery Problem is Solvable in Polynomial Time

T0 review · 3 major / 5 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 This paper proves that the contiguous art gallery problem—partitioning a simple polygon's boundary into the fewest contiguous chains each visible to one guard—is solvable in polynomial time by a simple repeated greedy sweep.

desk verdict A genuinely new polynomial-time result for a natural art gallery variant, with a sound greedy analysis and a fixable degeneracy gap in the geometric proof. read the letter →

arxiv 2412.13938 v3 pith:ZR3QBINF submitted 2024-12-18 cs.CG

Magnus Christian Ring Merrild , Casper Moldrup Rysgaard , Jens Kristian Refsgaard Schou , Rolf Svenning This is my paper · ORCID
classification cs.CG MSC 68U0568Q25
keywords artgalleryproblemcontiguousgreedyalgorithmsimplepolygonboundarypartitionvisibilitycomputationalgeometrypolynomial-time
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 proves that the contiguous art gallery problem, a 2024 variant of the classical art gallery problem, is solvable in polynomial time. The task is to partition the boundary of a simple polygon into the minimum number of contiguous chains such that each chain is visible from a single guard. The authors give a greedy algorithm that repeatedly takes the longest visible interval from a point on the boundary, and prove that after polynomially many revolutions it must reach an optimal partition. The running time is $O(k^* n^5 \log n)$ arithmetic operations, where $n$ is the number of vertices and $k^*$ is the size of an optimal solution; a bit-complexity analysis places the problem in the complexity class $\mathrm{P}$. This stands in contrast to most art gallery variants, which are NP-hard or $\exists\mathbb{R}$-complete.

What carries the argument

The load-bearing object is the greedy interval map $G(x)$ and its iterates, called the greedy sequence. A greedy interval is the longest contiguous boundary chain starting at $x$ that is visible to a single guard; the feasible region of a chain is the intersection of visibility polygons of all points on the chain, and its structure is controlled by pivot lines—lines through pairs of blocking vertices that limit the guard's sight. The argument splits into two cases: when the feasible region lies strictly above the pivot line, any repeated pivot line forces a repetition or an edge jump; when it reaches or dips below the pivot line, a separate analysis shows that some later guard is forced above its own pivot line, eventually triggering a progress condition. The combinatorial spine consists of three optimality certificates—positive fingerprint, periodic repetition, and $n+1$ edge jumps—any of which provably occurs within $O(k n^2)$ revolutions.

What would settle it

Construct a simple polygon in which the blocking polygon of Definition 8 necessarily self-intersects for every choice of backtracking distance, causing GreedyInterval's lastVisiblePoint computation to fail; or exhibit a polygon where the greedy sequence runs for more than $c k^* n^2$ revolutions with no positive fingerprint, repetition, or $n+1$ edge jumps for any fixed constant $c$.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1: for a simple polygon with $n$ vertices, the contiguous art gallery problem can be solved in $O(k^* n^5 \log n)$ arithmetic operations, where $k^*$ is the minimum number of chains in an optimal solution. Theorem 2 strengthens this to the bit-complexity RAM model: when the polygon is encoded in $N$ bits, the problem lies in $\mathrm{P}$. The proof is constructive: the GreedyInterval algorithm computes, for a given boundary point $x$, the farthest boundary point $y$ such that the chain $[x,y]$ is visible to some interior guard. Iterating this map generates a greedy sequence; the paper shows that within $O(k^* n^2)$ revolutions, the sequence must exhibit one of three progress conditions—a positive fingerprint, an exact repetition, or $n+1$ edge jumps—each of which certifies optimality. Repeating this $n+1$ times yields an optimal partition, and the bit-complexity section bounds the size of all computed coordinates, giving the $\mathrm{P}$ membership.

Load-bearing premise

The proof relies on being able to perturb the geometry by 'a small bit'—in the construction of the blocking polygon and in excluding edge cases—without changing the greedy algorithm's output, and no rigorous existence proof for such perturbations is given.

Editorial extensions

If this is right

  • The contiguous art gallery problem for simple polygons is in $\mathrm{P}$; it is not NP-hard (assuming $\mathrm{P} \neq \mathrm{NP}$), unlike the classical and edge-covering art gallery problems.
  • An optimal partition can be found in $O(k^* n^5 \log n)$ arithmetic operations on a real RAM, and the same bound carries over as a polynomial-time RAM algorithm on an $N$-bit encoding.
  • Vertex-restricted variants are faster: guarding from vertices runs in $O(n^2 \log n)$ time, and restricting chain endpoints to vertices runs in $O(n^2 \log^2 n)$ time.
  • A practical C++ implementation is available, and empirical tests suggest that the greedy algorithm typically finds an optimal solution within four revolutions, far below the proven bound.

Reading between the lines

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

  • If the authors' conjecture that a constant number of revolutions suffice is correct, the same algorithm would run in $O(n^2 \log n)$, making the greedy sweep essentially optimal up to the cost of computing visibility polygons.
  • The pivot-line argument is a potential template for other boundary-covering problems: any greedy map on a circle whose progress is measured by finitely many obstacle lines may admit a polynomial revolution bound by pigeonhole plus local perturbation.
  • The two informal 'small enough' perturbation arguments are the main gap to a fully formal proof; replacing them with a symbolic perturbation scheme would close the gap without changing the algorithm's structure.
  • The superpolynomial example for polygons with holes in Appendix C.2 suggests the polynomial bound is specific to hole-free polygons, and any extension to holes would need genuinely new ideas.
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 / 5 minor

Summary. The paper studies the contiguous art gallery problem, in which the boundary of a simple polygon must be partitioned into a minimum number of polygonal chains, each visible to some guard in the interior. The authors describe a greedy algorithm that repeatedly computes the longest visible interval from the current boundary point, and they claim that after polynomially many revolutions the greedy sequence contains an optimal solution. The main theoretical results are Theorem 1, an O(k* n^5 log n) arithmetic-operation bound on the real RAM, and Theorem 2, membership in P via a bit-complexity analysis. The combinatorial part (Section 4) establishes structural properties of greedy sequences, including optimality conditions based on fingerprints, repetitions, and edge jumps. The geometric part (Section 5) analyzes feasible regions and pivot lines to prove that a progress condition must occur within O(k n^2) revolutions. Appendices cover vertex-restricted variants, supporting lemmas, and an example showing that the algorithm fails for polygons with holes.

Significance. If the proof is correct, this is a striking result: the contiguous art gallery problem would be one of the few unrestricted art-gallery variants known to be polynomial-time solvable, in contrast to the classical and edge-covering variants that are ∃R-complete. The paper also provides a C++ implementation and a careful bit-complexity argument, which are valuable. The combinatorial framework in Section 4 is elegant and rigorous, and the proposed algorithm is genuinely simple. However, the geometric analysis contains several informal infinitesimal perturbation arguments, and these are load-bearing for the main theorem. The result is therefore significant but not yet fully established as written.

major comments (3)
  1. [Definition 8 and Lemma 9-11 (§3.3)] The construction of the blocking polygon B in Definition 8 is not a well-defined geometric procedure: it refers to moving "a little to the left", "back up a small bit", and choosing distances "small enough" without specifying how these choices are made or proving that they can be made simultaneously in every degenerate configuration. Lemma 9 (disjointness of B and F_{i-1}) and Lemma 11 (that L(g,c) is a common tangent) depend on this construction, and therefore the correctness of lastVisiblePoint, Theorem 3, and every downstream step inherits the gap. The paper needs either a formal perturbation scheme (e.g., symbolic perturbation) or a general-position assumption with an argument that the computed greedy endpoint is obtained as a limit of perturbed endpoints.
  2. [Remark 41 (§5.2)] The assertion that replacing F by F([y-ε,z+ε]) "will not impact the other proofs" is load-bearing. Lemma 42 explicitly relies on Remark 41 to rule out z lying above L(a,C_{z,i}), and Lemma 42 is needed for Lemma 43 and Proposition 44, which in turn is essential for Theorem 37. No proof is given that such an ε exists for every relevant step of the greedy sequence while preserving the computed endpoints and guards; for degenerate inputs it is conceivable that every positive ε changes the greedy sequence or fails to make the required geometric inequalities strict. This is a gap in the proof of Theorem 37.
  3. [Proposition 48 (§5.3)] Proposition 48 is the core of the "feasible region below pivot line" case, but its proof is a long case analysis that relies heavily on figures and unstated geometric properties. For example, the paragraph before Figure 31 asserts that "both edges in ∂P connected to x will point downwards" without proof, and Subcase 3.2 relies on the assertion that the ray from the guard through the pivot is contained in Q_i. These claims are not established, and the terminal conditions are asserted rather than derived from the preceding geometry. Since Proposition 48 is used to show that repeated pivot lines lead to a progress condition, Theorem 37 is not fully supported until these cases are proved in detail.
minor comments (5)
  1. [Section 2, Algorithm 1] The update rule for j on line 4 uses the condition j ≤ T−2 and then returns intervals {j < i ≤ T}; it is unclear why T−2 appears rather than an index naturally derived from the definition of a revolution, and this off-by-one behavior should be clarified.
  2. [Theorem 21] The proof refers to "at least k−1 endpoints" while the statement and the preceding definition of a revolution involve k+1 steps; the indexing should be made consistent and the bound k ≤ k*+1 should be verified directly.
  3. [Appendix B.2] The sentence "Since we only look at blockage (Remark 21)" refers to a nonexistent remark; the intended reference appears to be Remark 6.
  4. [Lemma 51] The displayed formulas for t_n and t_d are difficult to verify and appear to contain at least one missing parenthesis; a shorter derivation using a standard line-intersection determinant formula would make the bit-complexity argument more readable.
  5. [Section 5.3, paragraph before Figure 31] The statement that both edges incident to x "point downwards" is not obvious from the definition of x as the furthest point below the pivot line inside the triangle and should be proved or restated as a separate lemma.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the derivation is self-contained and the informal perturbation passages are rigor gaps, not input–output equivalences.

full rationale

The paper's derivation chain is not circular. The greedy algorithm is defined by a primitive (GreedyInterval) that computes farthest visible endpoints; no parameter is fitted to the target value k*, and k* appears only in the output-sensitive runtime bound as an instance parameter, not as an input to the algorithm. The optimality conditions (positive fingerprint, repetition, edge jumps) are derived from combinatorial axioms (Lemma 17, Corollaries 19, 30–32) using standard interval-cover arguments, not from the claimed polynomial bound. The geometric proof of Theorem 37 uses a pivot-line pigeonhole argument with the number of possible pivot lines bounded by O(n^2), and the repeated-feasible-region cases are handled by Proposition 44 and Proposition 48; these are independent geometric arguments. The bit-complexity analysis in Section 6 is self-contained and does not assume the main theorem's conclusion. The paper's self-citations (its own code repository [25] and the merged SoCG paper [7]) are not load-bearing for the correctness proof. The only notable weaknesses are in Definition 8 and Remark 41, where 'small bit' and 'small enough' backtracking, and the replacement of F by F([y−ε, z+ε]) for an 'arbitrary small ε', are asserted without a formal general-position or symbolic-perturbation proof. These are correctness and rigor risks potentially affecting Theorem 37, but they do not make any claimed result equivalent to its inputs by construction. No fitted-input-called-prediction, self-citation-forced uniqueness, or ansatz-smuggling pattern is present. The derivation is therefore self-contained for the purpose of circularity analysis, and the appropriate score is 0.

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

The central claim rests on standard geometric primitives (visibility polygons, polygon clipping, common tangents) and on the topological properties of simple polygons. The main non-standard, load-bearing assumption is the existence of infinitesimal perturbations that avoid degeneracies without changing the algorithm's behavior; this is used in the blocking-polygon construction and in the pivot-line analysis. No free parameters are fitted to data, and no new entities are introduced.

assumptions (4)
  • domain assumption The input polygon is simple and has no holes.
    The algorithm and analysis apply only to simple polygons without holes; holes make the problem open and the greedy algorithm can run in superpolynomial time (Example 59).
  • domain assumption The cited subroutines (visibility polygon, polygon intersection, common tangents) compute exact results within the stated time bounds.
    GreedyInterval relies on these black-box primitives; the paper cites them but does not prove them.
  • ad hoc to paper Infinitesimal perturbations ('small enough', 'very close') can be used to avoid degenerate configurations without changing the greedy behavior or the pivot-line analysis.
    Used in Definition 8 to construct the blocking polygon and in Remark 41 to fix special cases. The text does not state a general-position assumption or prove that such perturbations preserve the value of GreedyInterval.
  • standard math The boundary of a simple polygon is a topological circle and interval containment on the boundary corresponds to chain containment.
    Section 4 maps the polygon to a circle representation for the combinatorial analysis.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Contiguous Art Gallery Problem is Solvable in Polynomial Time." pith.science (2026). https://pith.science/paper/ZR3QBINF

@misc{pith2026241213938,
  author       = {Pith},
  title        = {Pith review of: The Contiguous Art Gallery Problem is Solvable in Polynomial Time},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZR3QBINF}},
  note         = {Machine review of arXiv:2412.13938}
}
abstract

In this paper, we study the Contiguous Art Gallery Problem, introduced by Thomas C. Shermer at the 2024 Canadian Conference on Computational Geometry, a variant of the classical art gallery problem from 1973 by Victor Klee. In the contiguous variant, the input is a simple polygon $P$, and the goal is to partition the boundary into a minimum number of polygonal chains such that each chain is visible to a guard. We present a polynomial-time RAM algorithm, which solves the contiguous art gallery problem. Our algorithm is simple and practical, and we make a C++ implementation available. In contrast, many variations of the art gallery problem are at least NP-hard, making the contiguous variant stand out. These include the classical art gallery problem and the edge-covering problem, both of which being proven to be $\exists\mathbb{R}$-complete recently by Abrahamsen, Adamaszek, and Miltzow [J. ACM 2022] and Stade [SoCG 2025], respectively. Our algorithm is a greedy algorithm that repeatedly traverses the polygon's boundary. To find an optimal solution, we show that it is sufficient to traverse the polygon polynomially many times, resulting in a runtime of $\mathcal{O}\!\left( n^6 \log n \right)$ arithmetic operations. We further bound the bit complexity of the computed values, showing that problem is in P. Additionally, we provide algorithms for the restricted settings, where either the endpoints of the polygonal chains or the guards must coincide with the vertices of the polygon.

Figures

Figures reproduced from arXiv: 2412.13938 by the authors.

Figure 9
Figure 9. Thus, to find lastV isibleP oint(P, Fi−1, ei−1) we can run the CommonTangents algorithm of Abrahamsen and Walczak [3] to find all common tangents (of which there are at most four) and manually check them to find the guard position that sees the most of ei−1. The claims will be proven in the following. ▶ Lemma 9 (Disjoint). B and Fi−1 are disjoint. Proof. Fi−1 is contained in the free area and B is contained below tm… view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 3 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 Analytic Arc Cover Problem and its Applications to Contiguous Art Gallery, Polygon Separation, and Shape Carving

    cs.CG 2024-12 conditional novelty 8.0 of 10

    Three geometric problems, contiguous art gallery, segment separation, and 3D half-plane carving minimization, are shown to be in P via the analytic arc cover framework.

  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.

Reference graph

Works this paper leans on

36 extracted references · 15 canonical work pages · cited by 3 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), December 2021. https://doi.org/10.1145/3486220 doi:10.1145/3486220

    doi:10.1145/3486220 2021

  2. [2]

    Minimum star partitions of simple polygons in polynomial time

    Mikkel Abrahamsen, Joakim Blikstad, Andr\' e Nusser, and Hanwen Zhang. Minimum star partitions of simple polygons in polynomial time. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , STOC 2024, page 904–910, New York, NY, USA, 2024. Association for Computing Machinery. https://doi.org/10.1145/3618260.3649756 doi:10.1145/3618260.3649756

    arXiv 2024

  3. [3]

    Common tangents of two disjoint polygons in linear time and constant workspace

    Mikkel Abrahamsen and Bartosz Walczak. Common tangents of two disjoint polygons in linear time and constant workspace. ACM Trans. Algorithms , 15(1), December 2018. https://doi.org/10.1145/3284355 doi:10.1145/3284355

    work page doi:10.1145/3284355 2018

  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]

    An optimal algorithm for determining the visibility of a polygon from an edge

    Avis and Toussaint. An optimal algorithm for determining the visibility of a polygon from an edge. IEEE Transactions on Computers , C-30(12):910--914, 1981. https://doi.org/10.1109/TC.1981.1675729 doi:10.1109/TC.1981.1675729

    arXiv 1981

  6. [6]

    Algorithms for reporting and counting geometric intersections

    Bentley and Ottmann. Algorithms for reporting and counting geometric intersections. IEEE Transactions on Computers , C-28(9):643--647, 1979. https://doi.org/10.1109/TC.1979.1675432 doi:10.1109/TC.1979.1675432

    arXiv 1979

  7. [7]

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

    2025

  8. [8]

    Ahmad Biniaz, Anil Maheshwari, Joseph S. B. Mitchell, Saeed Odak, Valentin Polishchuk, and Thomas Shermer. Contiguous boundary guarding, 2024. URL: https://arxiv.org/abs/2412.15053, https://arxiv.org/abs/2412.15053 arXiv:2412.15053

    arXiv 2024

Show all 36 references
  1. [9]

    Complexity and Real Computation

    Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale. Complexity and Real Computation . Springer New York, 1998. https://doi.org/10.1007/978-1-4612-0701-6 doi:10.1007/978-1-4612-0701-6

    1998 doi

  2. [10]

    A linear algorithm for computing the visibility polygon from a point

    H El Gindy and D Avis. A linear algorithm for computing the visibility polygon from a point. Journal of Algorithms , 2(2):186--197, 1981. https://doi.org/10.1016/0196-6774(81)90019-5 doi:10.1016/0196-6774(81)90019-5

    1981 doi

  3. [11]

    On the design of cgal a computational geometry algorithms library

    Andreas Fabri, Geert-Jan Giezeman, Lutz Kettner, Stefan Schirra, and Sven Sch \"o nherr. On the design of cgal a computational geometry algorithms library. Software: Practice and Experience , 30(11):1167--1202, 2000

    2000

  4. [12]

    2D regularized boolean set-operations

    Efi Fogel, Ophir Setter, Ron Wein, Guy Zucker, Baruch Zukerman, and Dan Halperin. 2D regularized boolean set-operations. In CGAL User and Reference Manual . CGAL Editorial Board , 6.0.1 edition, 2024. URL: https://doc.cgal.org/6.0.1/Manual/packages.html#PkgBooleanSetOperations2

    2024

  5. [13]

    Intersection of two lines in three-space

    Ronald Goldman. Intersection of two lines in three-space. In ANDREW S. GLASSNER, editor, Graphics Gems , page 304. Morgan Kaufmann, San Diego, 1990. https://doi.org/10.1016/B978-0-08-050753-8.50064-4 doi:10.1016/B978-0-08-050753-8.50064-4

    1990 doi

  6. [14]

    Efficient clipping of arbitrary polygons

    G\" u nther Greiner and Kai Hormann. Efficient clipping of arbitrary polygons. ACM Trans. Graph. , 17(2):71–83, April 1998. https://doi.org/10.1145/274363.274364 doi:10.1145/274363.274364

    1998

  7. [15]

    Geometric Algorithms and Combinatorial Optimization , volume 2 of Algorithms and Combinatorics

    Martin Gr \" o tschel, L \' a szl \' o Lov \' a sz, and Alexander Schrijver. Geometric Algorithms and Combinatorial Optimization , volume 2 of Algorithms and Combinatorics . Springer, 1988. https://doi.org/10.1007/978-3-642-97881-4 doi:10.1007/978-3-642-97881-4

    1988 doi

  8. [16]

    2D visibility computation

    Michael Hemmer, Kan Huang, Francisc Bungiu, and Ning Xu. 2D visibility computation. In CGAL User and Reference Manual . CGAL Editorial Board , 6.0.1 edition, 2024. URL: https://doc.cgal.org/6.0.1/Manual/packages.html#PkgVisibility2

    2024

  9. [17]

    Mark Keil

    J. Mark Keil. Decomposing a polygon into simpler components. SIAM Journal on Computing , 14(4):799--817, 1985. https://doi.org/10.1137/0214056 doi:10.1137/0214056

    1985 doi

  10. [18]

    Mark Keil and Jorg-R

    J. Mark Keil and Jorg-R. Sack. Minimum decompositions of polygonal objects. In Godfried T. TOUSSAINT, editor, Computational Geometry , volume 2 of Machine Intelligence and Pattern Recognition , pages 197--216. North-Holland, 1985. https://doi.org/10.1016/B978-0-444-87806-9.500...

    1985 doi

  11. [19]

    Guarding the walls of an art gallery

    Aldo Laurentini. Guarding the walls of an art gallery. The Visual Computer , 15(6):265--278, 1999. https://doi.org/10.1007/S003710050177 doi:10.1007/S003710050177

    1999 doi

  12. [20]

    Lee and D.T

    C.C. Lee and D.T. Lee. On a circle-cover minimization problem. Information Processing Letters , 18(2):109--115, 1984. https://doi.org/10.1016/0020-0190(84)90033-4 doi:10.1016/0020-0190(84)90033-4

    1984 doi

  13. [21]

    Lee and A

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

    1986

  14. [22]

    D. T. Lee and Arthur K. Lin. Computational Complexity of Art Gallery Problems , pages 303--309. Springer New York, New York, NY, 1990. https://doi.org/10.1007/978-1-4613-8997-2_23 doi:10.1007/978-1-4613-8997-2_23

    1990 doi

  15. [23]

    Mark Keil

    J. Mark Keil . Chapter 11 - polygon decomposition. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry , pages 491--518. North-Holland, Amsterdam, 2000. https://doi.org/10.1016/B978-044482537-7/50012-7 doi:10.1016/B978-044482537-7/50012-7

    doi

  16. [24]

    A new algorithm for computing boolean operations on polygons

    Francisco Martínez, Antonio Jesús Rueda, and Francisco Ramón Feito. A new algorithm for computing boolean operations on polygons. Computers & Geosciences , 35(6):1177--1185, 2009. https://doi.org/10.1016/j.cageo.2008.08.009 doi:10.1016/j.cageo.2008.08.009

    2009 doi

  17. [25]

    Magnus C. R. Merrild, Casper M. Rysgaard, Jens K. R. Schou, and Rolf Svenning. An Algorithm for the Contiguous Art Gallery Problem in . https://github.com/RolfSvenning/ContiguousArtGallery, 2024

    2024

  18. [26]

    Art gallery theorems and algorithms

    Joseph O'Rourke. Art gallery theorems and algorithms . Oxford University Press, Inc., USA, 1987

    1987

  19. [27]

    Dynamization of order decomposable set problems

    Mark H Overmars. Dynamization of order decomposable set problems. Journal of Algorithms , 2(3):245--260, 1981. https://doi.org/10.1016/0196-6774(81)90025-0 doi:10.1016/0196-6774(81)90025-0

    1981 doi

  20. [28]

    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, 2024. URL: https://arxiv.org/abs/2412.15567, https://arxiv.org/abs/2412.15567 arXiv:2412.15567

    2024 arXiv

  21. [29]

    Fixed points, nash equilibria, and the existential theory of the reals

    Marcus Schaefer and Daniel \' z Tefankovi a \' z . Fixed points, nash equilibria, and the existential theory of the reals. Theor. Comp. Sys. , 60(2):172–193, February 2017. https://doi.org/10.1007/s00224-015-9662-0 doi:10.1007/s00224-015-9662-0

    2017 doi

  22. [30]

    Thomas C. Shermer. Recent results in art galleries (geometry). Proc. IEEE , 80(9):1384--1399, 1992. https://doi.org/10.1109/5.163407 doi:10.1109/5.163407

    1992 doi

  23. [31]

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

    2025 doi

  24. [32]

    CGAL User and Reference Manual

    The CGAL Project . CGAL User and Reference Manual . CGAL Editorial Board , 6.0.1 edition, 2024. URL: https://doc.cgal.org/6.0.1/Manual/packages.html

    2024

  25. [33]

    Art gallery and illumination problems

    Jorge Urrutia. Art gallery and illumination problems. Handbook of Computational Geometry , 12 2000. https://doi.org/10.1016/B978-044482537-7/50023-1 doi:10.1016/B978-044482537-7/50023-1

    2000 doi

  26. [34]

    Bala R. Vatti. A generic solution to polygon clipping. Commun. ACM , 35(7):56–63, July 1992. https://doi.org/10.1145/129902.129906 doi:10.1145/129902.129906

    1992

  27. [35]

    Hidden surface removal using polygon area sorting

    Kevin Weiler and Peter Atherton. Hidden surface removal using polygon area sorting. SIGGRAPH Comput. Graph. , 11(2):214–222, July 1977. https://doi.org/10.1145/965141.563896 doi:10.1145/965141.563896

    1977

  28. [36]

    2D arrangements

    Ron Wein, Eric Berberich, Efi Fogel, Dan Halperin, Michael Hemmer, Oren Salzman, and Baruch Zukerman. 2D arrangements. In CGAL User and Reference Manual . CGAL Editorial Board , 6.0.1 edition, 2024. URL: https://doc.cgal.org/6.0.1/Manual/packages.html#PkgArrangementOnSurface2

    2024

Pith tools

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