pith. sign in

arxiv: 2511.02960 · v5 · submitted 2025-11-04 · 💻 cs.CG · cs.DS

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

Sarita de Berg , Jacobus Conradi , Ivor van der Hoog , Eva Rotenberg This is my paper

Pith reviewed 2026-05-18 01:01 UTC · model grok-4.3

classification 💻 cs.CG cs.DS
keywords Contiguous Art GalleryArt Gallery ProblemSimple PolygonsVisibility PartitioningTime ComplexityLower BoundsSet IntersectionReal RAM Model
0
0 comments X

The pith

The contiguous art gallery problem on simple polygons can be solved in Theta(n log n) time.

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

The paper establishes that partitioning the boundary of a simple polygon into the smallest number of contiguous segments, each fully visible from some interior point, requires and admits Theta(n log n) time in the real RAM model. It does this by giving an O(n log n) algorithm and a matching Omega(n log n) lower bound obtained through a direct reduction from the set intersection problem. Earlier solutions needed O(k n^5 log n) or O(n^6 log n) time, so the new result removes large polynomial factors and shows the problem is solvable at the sorting lower bound. A reader cares because the result settles the asymptotic complexity of this natural variant of the art gallery problem.

Core claim

The authors give an O(n log n)-time algorithm for computing the minimal contiguous visibility partition of a simple polygon's boundary together with a sorting-based Omega(n log n) lower bound obtained by reducing from the set intersection problem. These two results together place the Contiguous Art Gallery problem in Theta(n log n) in the real RAM model and improve prior running times by a factor of O(k n^4).

What carries the argument

A sorting-based reduction from the set intersection problem that directly encodes the hardness of determining the minimal number of contiguous visible segments on the boundary of a simple polygon.

If this is right

  • The minimal number of contiguous visible boundary segments can be computed in optimal time for any simple polygon.
  • High-degree polynomial factors that appeared in earlier algorithms are unnecessary for this problem.
  • The real RAM model suffices to achieve and prove the tight bound for this visibility partitioning task.
  • The same sorting hardness applies to the decision version of finding the smallest such partition.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The reduction technique could be adapted to establish similar tight bounds for other contiguous geometric partitioning problems on polygons.
  • Efficient implementations of the new algorithm might enable faster visibility-based tasks in applications such as sensor placement or architectural analysis.
  • The result suggests that many polygon-boundary optimization problems may have true complexity governed by sorting rather than higher-degree polynomials.

Load-bearing premise

The set intersection problem reduces to contiguous visibility partitioning without losing the Omega(n log n) lower bound in the real RAM model.

What would settle it

An algorithm that computes the optimal contiguous partition for every simple polygon in o(n log n) time, or an explicit simple polygon instance where the minimal partition size can be found with fewer than Omega(n log n) comparisons, would falsify the claimed bound.

Figures

Figures reproduced from arXiv: 2511.02960 by Eva Rotenberg, Ivor van der Hoog, Jacobus Conradi, Sarita de Berg.

Figure 1
Figure 1. Figure 1: A simple polygon P and five contiguous guards that guard the entire boundary of P. 1 [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The lower-bound construction. Black points belong to [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Flowchart illustrating how a guard is dominated. We prove the green block in [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The visibility core E[i − 1, j + 1] in green and the segment-intersecting dominator (g, [umax, vmax]) for (i, j). i j i − 1 j + 1 = vmax g umax vmax [PITH_FULL_IMAGE:figures/full_fig_p010_4.png] view at source ↗
Figure 6
Figure 6. Figure 6: Case 2 of Lemma 5. The point g ∗ that has ∢(i, g∗ , j) = α is in the visibility core E[u, v] (green), but not in Pg (gray). Let e ∈ E be the edge defining ℓ. By definition, e lies on ℓ and thus ℓ separates e from i and j. Consider the directed line ℓj from the right endpoint of e to j, and consider the chain from e’s right endpoint to j. This chain must contain at least one edge e ∗ whose start lies left o… view at source ↗
Figure 7
Figure 7. Figure 7: The shortest path from u to j + 1 (red), and E[i − 1, j + 1] (green). Any point that sees both u and v lies in the blue wedge. g u v r g ′ [PITH_FULL_IMAGE:figures/full_fig_p012_7.png] view at source ↗
Figure 9
Figure 9. Figure 9: The inclusion-wise maximal area visible from [PITH_FULL_IMAGE:figures/full_fig_p016_9.png] view at source ↗
Figure 11
Figure 11. Figure 11: No point in the blue polygon can be in the visibility core E[i − 1, j′ + 1]. i j j ′ g [PITH_FULL_IMAGE:figures/full_fig_p018_11.png] view at source ↗
Figure 14
Figure 14. Figure 14: Illustration of non-optimal solution of size 5, induced by u ∈ ∂P that is a vertex of P. The guard gi is the realizing guard/dominator for [nexti−1 (u), nexti (u)]. 23 [PITH_FULL_IMAGE:figures/full_fig_p024_14.png] view at source ↗
Figure 15
Figure 15. Figure 15: Construction of three guards guarding all of [PITH_FULL_IMAGE:figures/full_fig_p028_15.png] view at source ↗
Figure 16
Figure 16. Figure 16: Construction of the points ps and pt by transforming the green triangle defined by s, t, and z into the light green triangle. 28 [PITH_FULL_IMAGE:figures/full_fig_p029_16.png] view at source ↗
Figure 17
Figure 17. Figure 17: The set Lx is not necessarily con￾nected, but for any two points u and u ′ in Lx, the vertex x stays on the shortest path for any uˆ in between u and u ′ , i.e., uˆ ∈ Ix. u ′ x u next(u) next(u ′ ) y g ′ [PITH_FULL_IMAGE:figures/full_fig_p030_17.png] view at source ↗
Figure 19
Figure 19. Figure 19: The lower bound construction. Black points are in the set [PITH_FULL_IMAGE:figures/full_fig_p033_19.png] view at source ↗
Figure 20
Figure 20. Figure 20: Illustration of a set of guards guard￾ing the outer boundary of a polygon P with a hole. The solution cannot readily be trans￾formed via Theorem 7 to have at least one good guard. g1 g2 g3 g4 u next4 (u) [PITH_FULL_IMAGE:figures/full_fig_p035_20.png] view at source ↗
read the original abstract

Recently, a natural variant of the Art Gallery problem, known as the \emph{Contiguous Art Gallery problem} was proposed. Given a simple polygon $P$, the goal is to partition its boundary $\partial P$ into the smallest number of contiguous segments such that each segment is completely visible from some point in $P$. Unlike the classical Art Gallery problem, which is NP-hard, this variant is polynomial-time solvable. At SoCG~2025, three independent works presented algorithms for this problem, each achieving a running time of $O(k n^5 \log n)$ (or $O(n^6\log n)$), where $k$ is the size of an optimal solution. Interestingly, these results were obtained using entirely different approaches, yet all led to roughly the same asymptotic complexity, suggesting that such a running time might be inherent to the problem. We show that this is not the case. In the real RAM-model, the prevalent model in computational geometry, we present an $O(n \log n)$-time algorithm, achieving an $O(k n^4)$ factor speed-up over the previous state-of-the-art. We also give a straightforward sorting-based lower bound by reducing from the set intersection problem. We thus show that the Contiguous Art Gallery problem is in $\Theta(n \log n)$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper presents an O(n log n)-time algorithm for the Contiguous Art Gallery problem on a simple polygon with n vertices in the real RAM model, together with an Omega(n log n) lower bound obtained by a direct reduction from the set intersection problem. This establishes a tight Theta(n log n) bound, improving by an O(k n^4) factor over the O(k n^5 log n) algorithms from three independent SoCG 2025 submissions.

Significance. If the result holds, it provides the first tight complexity bound for this natural variant of the art gallery problem. The improvement from quintic to near-linear time is substantial, and the sorting-based lower bound is a clean, model-appropriate contribution that may inform other visibility partitioning tasks. The manuscript ships a self-contained algorithmic construction and an explicit reduction, both of which are strengths.

minor comments (3)
  1. The abstract and introduction cite the three SoCG 2025 works but do not include a brief comparison table of their running times and techniques; adding one would help readers situate the new O(n log n) result.
  2. Section 3 (algorithm description) uses the term 'sweep-line visibility partitioning' without an accompanying figure or pseudocode snippet; a small illustrative diagram of the sweep would improve clarity for readers unfamiliar with the prior O(n^5 log n) methods.
  3. The reduction in Section 4 maps set-intersection instances to contiguous partitions but does not explicitly state the real-RAM operations used to simulate the intersection queries; a one-sentence clarification would remove any ambiguity about model assumptions.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive review and for recommending acceptance. We appreciate the recognition that our O(n log n) algorithm and matching lower bound establish the first tight complexity result for the Contiguous Art Gallery problem and improve substantially on the prior O(k n^5 log n) bounds.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The paper derives an O(n log n) upper bound via an explicit algorithmic construction (sweep-line or sorting-based visibility partitioning on simple polygons) and an Omega(n log n) lower bound via a direct reduction from the external set intersection problem in the real RAM model. Neither step reduces to a fitted parameter, self-citation chain, or definitional equivalence within the paper; the lower bound imports an independent known complexity result, and the upper bound is a novel construction that does not presuppose the claimed Theta bound. The manuscript is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on the standard real RAM model for geometric algorithms and the assumption that simple polygons admit the visibility relations used in the reduction and algorithm.

axioms (2)
  • domain assumption Arithmetic operations on real numbers take constant time (real RAM model).
    Invoked for all time-complexity statements in computational geometry.
  • domain assumption The input is a simple polygon whose boundary visibility can be queried in the manner required by the reduction.
    Underlying both the algorithm and the set-intersection reduction.

pith-pipeline@v0.9.0 · 5779 in / 1288 out tokens · 85871 ms · 2026-05-18T01:01:29.648851+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

45 extracted references · 45 canonical work pages · 2 internal anchors

  1. [1]

    Irrational Guards are Sometimes Needed

    Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow. Irrational Guards are Sometimes Needed. InSymposium on Computational Geometry (SoCG), volume 77 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 3:1–3:15, Dagstuhl, Germany, 2017. Schloss Dagstuhl - Leibniz-Zentrum für Informatik.doi:10.4230/LIPIcs.SoCG.2017.3

    work page doi:10.4230/lipics.socg.2017.3 2017

  2. [2]

    The art gallery problem is∃ R-complete

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

    work page doi:10.1145/3188745.3188868 2018

  3. [3]

    Agarwal, Lars Arge, and Ke Yi

    Pankaj K. Agarwal, Lars Arge, and Ke Yi. An optimal dynamic interval stabbing-max data structure? InACM-SIAM Symposium on Discrete Algorithms (SODA), SODA ’05, page 803–812, USA, 2005. Society for Industrial and Applied Mathematics. URL:https: //dl.acm.org/doi/10.5555/1070432.1070546

    work page doi:10.5555/1070432.1070546 2005

  4. [4]

    Finding minimal convex nested polygons.Information and Computation, 83(1):98–110, 1989.doi: 10.1016/0890-5401(89)90049-7

    Alok Aggarwal, Heather Booth, Joseph O’Rourke, Subhash Suri, and Chee K Yap. Finding minimal convex nested polygons.Information and Computation, 83(1):98–110, 1989.doi: 10.1016/0890-5401(89)90049-7

    work page doi:10.1016/0890-5401(89)90049-7 1989

  5. [5]

    Masset, R

    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

    work page doi:10.1016/j 2017

  6. [6]

    On r-Guarding Thin Orthogonal Polygons

    Therese Biedl and Saeed Mehrabi. On r-Guarding Thin Orthogonal Polygons. InInternational Symposium on Algorithms and Computation (ISAAC), volume 64 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 17:1–17:13, Dagstuhl, Germany, 2016. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL:https://drops.dagstuhl.de/entities/ document/10.42...

    work page doi:10.4230/lipics.isaac.2016.17 2016

  7. [7]

    Grid-obstacle representations with connections to staircase guarding

    Therese Biedl and Saeed Mehrabi. Grid-obstacle representations with connections to staircase guarding. InGraph Drawing and Network Visualization (GD), volume 10692 ofLecture Notes in Computer Science, pages 81–87. Springer, 2017.doi:10.1007/978-3-319-73915-1\_7

    work page doi:10.1007/978-3-319-73915-1 2017

  8. [8]

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

    work page doi:10.4230/lipics.socg.2025.20 2025

  9. [9]

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

    work page arXiv 2024

  10. [10]

    Parameterized hardness of art gallery problems.ACM Transactions on Algorithms, 16(4), 2020.doi:10.1145/3398684

    Édouard Bonnet and Tillmann Miltzow. Parameterized hardness of art gallery problems.ACM Transactions on Algorithms, 16(4), 2020.doi:10.1145/3398684

    work page doi:10.1145/3398684 2020

  11. [11]

    Dynamic planar convex hull

    Gerth Stølting Brodal and Riko Jacob. Dynamic planar convex hull. InSymposium on Foundations of Computer Science (FOCS), pages 617–626. IEEE, IEEE Computer Society, 2002.doi:10.1109/SFCS.2002.1181985

    work page doi:10.1109/sfcs.2002.1181985 2002

  12. [12]

    Svante Carlsson, Håkan Jonsson, and Bengt J. Nilsson. Finding the shortest watchman route in a simple polygon.Discrete & Computational Geometry, 22(3):377–402, 1999.doi: 10.1007/PL00009467

    work page doi:10.1007/pl00009467 1999

  13. [13]

    Chan, John Hershberger, and Simon Pratt

    Timothy M. Chan, John Hershberger, and Simon Pratt. Two approaches to building time- windowed geometric data structures.Algorithmica, 81(9):3519–3533, 2019. doi:10.1007/ s00453-019-00588-3

    work page 2019

  14. [14]

    D. Z. Chen, V. Estivill-Castro, and J. Urrutia. Optimal guarding of polygons and monotone chains. InCanadian Conference on Computational Geometry (CCCG), pages 133–138. Carleton University, Ottawa, Canada, 1995

    work page 1995

  15. [15]

    Shortest watchman routes in simple polygons.Discrete & Computational Geometry, 6(1):9–31, 1991.doi:10.1007/BF02574671

    Wei-Pang Chin and Simeon Ntafos. Shortest watchman routes in simple polygons.Discrete & Computational Geometry, 6(1):9–31, 1991.doi:10.1007/BF02574671

    work page doi:10.1007/bf02574671 1991

  16. [16]

    Optimum watchman routes.Information Processing Letters, 28(1):39–44, 1988.doi:10.1145/10515.10518

    Wen-Chang Chin and Simeon Ntafos. Optimum watchman routes.Information Processing Letters, 28(1):39–44, 1988.doi:10.1145/10515.10518

    work page doi:10.1145/10515.10518 1988

  17. [17]

    A combinatorial theorem in plane geometry.Journal of Combinatorial Theory, Series B, 18(1):39–41, 1975.doi:10.1016/0095-8956(75)90061-1

    Václav Chvátal. A combinatorial theorem in plane geometry.Journal of Combinatorial Theory, Series B, 18(1):39–41, 1975.doi:10.1016/0095-8956(75)90061-1

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

  18. [18]

    Dobkin and David G

    David P. Dobkin and David G. Kirkpatrick. Fast detection of polyhedral intersection.Theoretical Computer Science (TSC), 27:241–253, 1983.doi:10.1016/0304-3975(82)90120-7

    work page doi:10.1016/0304-3975(82)90120-7 1983

  19. [19]

    Adrian Dumitrescu and Csaba D. Tóth. Watchman tours for polygons with holes.Computational Geometry: Theory and Applications, 45(7):326–333, 2012.doi:10.1016/j.comgeo.2011.11. 005. 35

    work page doi:10.1016/j.comgeo.2011.11 2012

  20. [20]

    Trajectory Visibility

    Patrick Eades, Ivor van der Hoog, Maarten Löffler, and Frank Staals. Trajectory Visibility. In Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), volume 162 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 23:1–23:22, Dagstuhl, Germany, 2020. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.doi:10.4230/LIPIcs.SWAT.2020.23

    work page doi:10.4230/lipics.swat.2020.23 2020

  21. [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

    work page 2001

  22. [22]

    Guibas and J

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

    work page doi:10.1145/41958.41964 1987

  23. [23]

    Deterministic sorting in o(n log log n) time and linear space

    Yijie Han. Deterministic sorting in o(n log log n) time and linear space. InACM Symposium on Theory of Computing (STOC), STOC ’02, page 602–608, USA, 2002. Association for Computing Machinery.doi:10.1145/509907.509993

    work page doi:10.1145/509907.509993 2002

  24. [24]

    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. InACM-SIAM Symposium on Discrete Algorithms (SODA), SODA ’93, page 54–63, USA, 1993. Society for Industrial and Applied Mathematics. URL:https://dl.acm.org/doi/ 10.5555/313559.313611

    work page doi:10.5555/313559.313611 1993

  25. [25]

    On the complexity of half-guarding monotone polygons

    Hannah Miller Hillberg, Erik Krohn, and Alex Pahlow. On the complexity of half-guarding monotone polygons. InLatin American Symposium on Theoretical Informatics (LATIN), page 761–777, Berlin, Heidelberg, 2022. Springer-Verlag.doi:10.1007/978-3-031-20624-5_46

    work page doi:10.1007/978-3-031-20624-5_46 2022

  26. [26]

    Guarding Path Polygons with Orthogonal Visibility

    Hamid Hoorfar and Alireza Bagheri. Guarding path polygons with orthogonal visibility, 2017. arXiv:1709.01569

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  27. [27]

    Minimum Hidden Guarding of Histogram Polygons

    Hamid Hoorfar and Alireza Bagheri. Minimum hidden guarding of histogram polygons, 2017. arXiv:1708.05815

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  28. [28]

    Erik Krohn and Bengt J. Nilsson. The complexity of guarding monotone polygons. InCanadian Conference on Computational Geometry (CCCG), pages 167–172, Charlottetown, Prince Edward Island, Canada, 2012. CCCG

    work page 2012

  29. [29]

    Guarding the walls of an art gallery.The Visual Computer, 15(6):265–278, 1999.doi:10.1007/s003710050177

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

    work page doi:10.1007/s003710050177 1999

  30. [30]

    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

    work page doi:10.1109/tit.1986.1057165 1986

  31. [31]

    Lee and F

    D. Lee and F. Preparata. An optimal algorithm for finding the kernel of a polygon.Journal of the ACM (JACM), 26:415–421, 07 1979.doi:10.1145/322139.322142

    work page doi:10.1145/322139.322142 1979

  32. [32]

    Demaine, Takehiro Ito, Jun Kawahara, Masashi Kiyomi, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Kei Uchizawa, and Takeaki Uno

    Salma Sadat Mahdavi, Saeed Seddighin, and Mohammad Ghodsi. Covering orthogonal polygons with sliding k-transmitters.Theoretical Computer Science, 815:163–181, 2020. URL:https:// www.sciencedirect.com/science/article/pii/S030439752030092X, doi:10.1016/j.tcs. 2020.02.008

    work page doi:10.1016/j.tcs 2020

  33. [33]

    The contiguous art gallery problem is solvable in polynomial time, 2024

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

    work page arXiv 2024

  34. [34]

    Joseph S. B. Mitchell. Approximating watchman routes. InACM-SIAM Symposium on Discrete Algorithms (SODA), pages 844–855. SIAM, 2013.doi:10.1137/1.9781611973105.60

    work page doi:10.1137/1.9781611973105.60 2013

  35. [35]

    O’Rourke and K

    J. O’Rourke and K. Supowit. Some np-hard polygon decomposition problems.IEEE Transac- tions on Information Theory, 29(2):181–190, 1983.doi:10.1109/TIT.1983.1056648

    work page doi:10.1109/tit.1983.1056648 1983

  36. [36]

    Minimum r-star cover of class-3 orthogonal polygons

    Leonidas Palios and Petros Tzimas. Minimum r-star cover of class-3 orthogonal polygons. InInternational Workshop on Combinatorial Algorithms (IWOCA), page 286–297, Berlin, Heidelberg, 2014. Springer-Verlag.doi:10.1007/978-3-319-19315-1_25

    work page doi:10.1007/978-3-319-19315-1_25 2014

  37. [37]

    The dispersive art gallery problem.Computational Geometry: Theory and Applications, 117(C), February 2024.doi:10.1016/j.comgeo.2023

    Christian Rieck and Christian Scheffer. The dispersive art gallery problem.Computational Geometry: Theory and Applications, 117(C), February 2024.doi:10.1016/j.comgeo.2023. 102054

    work page doi:10.1016/j.comgeo.2023 2024

  38. [38]

    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. arXiv:2412.15567

    work page arXiv 2024

  39. [39]

    Two np-hard art-gallery problems for ortho-polygons.Mathematical Logic Quarterly, 41(2):261–267, 1995

    Dietmar Schuchardt and Hans-Dietrich Hecker. Two np-hard art-gallery problems for ortho-polygons.Mathematical Logic Quarterly, 41(2):261–267, 1995. doi:10.1002/malq. 19950410212

    work page doi:10.1002/malq 1995

  40. [40]

    In 32nd European Conference on Object-Oriented Programming (ECOOP 2018)

    Jack Stade. The Point-Boundary Art Gallery Problem Is∃R-Hard. InSymposium on Com- putational Geometry (SoCG), volume 332 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 74:1–74:23, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs. SoCG.2025.74,doi...

    work page doi:10.4230/lipics 2025

  41. [41]

    Fast computation of shortest watchman routes in simple polygons.Information Processing Letters, 77(1):27–33, 2001.doi:10.1016/S0020-0190(00)00146-0

    Xuehou Tan. Fast computation of shortest watchman routes in simple polygons.Information Processing Letters, 77(1):27–33, 2001.doi:10.1016/S0020-0190(00)00146-0

    work page doi:10.1016/s0020-0190(00)00146-0 2001

  42. [42]

    Guarding thin orthogonal polygons is hard

    Ana Paula Tomás. Guarding thin orthogonal polygons is hard. InFundamentals of Computation Theory (FCT), FCT’13, page 305–316, Berlin, Heidelberg, 2013. Springer-Verlag.doi:10.1007/ 978-3-642-40164-0_29

    work page 2013

  43. [43]

    Reflective guarding a gallery

    Arash Vaezi, Bodhayan Roy, and Mohammad Ghodsi. Reflective guarding a gallery. In WALCOM: Algorithms and Computation, page 78–89, Berlin, Heidelberg, 2023. Springer-Verlag. doi:10.1007/978-3-031-27051-2_8

    work page doi:10.1007/978-3-031-27051-2_8 2023

  44. [44]

    Polygon decomposition and the orthogonal art gallery problem

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

    work page doi:10.1142/s0218195907002264 2007

  45. [45]

    Lower bounds for algebraic computation trees with integer inputs

    Andrew Chi-Chih Yao. Lower bounds for algebraic computation trees with integer inputs. SIAM Journal on Computing, 20(4):655–668, 1991.doi:10.1137/0220041. 37

    work page doi:10.1137/0220041 1991