Polynomial-Time Algorithms for Contiguous Art Gallery and Related Problems

Biniaz, Ahmad; Maheshwari, Anil; Merrild, Magnus Christian Ring; Mitchell, Joseph S. B.; Odak, Saeed; Polishchuk, Valentin; Robson, Eliot W.; Rysgaard, Casper Moldrup; Schou, Jens Kristian Refsgaard; Shermer, Thomas; Spalding-Jamieson, Jack; Svenning, Rolf; Zheng, Da Wei

doi:10.4230/LIPIcs.SoCG.2025.20

Polynomial-Time Algorithms for Contiguous Art Gallery and Related Problems

Ahmad Biniaz

School of Computer Science, University of Windsor, Canada Anil Maheshwari

School of Computer Science, Carleton University, Canada Magnus Christian Ring Merrild

Department of Computer Science, Aarhus University, Denmark Joseph S. B. Mitchell

Department of Applied Mathematics and Statistics, Stony Brook University, NY, USA Saeed Odak

School of Electrical Engineering and Computer Science, University of Ottawa, Canada Valentin Polishchuk

Communications and Transport Systems, Linköping Univeristy, Sweden Eliot W. Robson

Department of Computer Science, University of Illinois Urbana-Champaign, IL, USA Casper Moldrup Rysgaard

Department of Computer Science, Aarhus University, Denmark Jens Kristian Refsgaard Schou

Department of Computer Science, Aarhus University, Denmark Thomas Shermer

School of Computing Science, Simon Fraser University, Burnaby, Canada Jack Spalding-Jamieson

Independent, Vancouver, Canada Rolf Svenning

Department of Computer Science, Aarhus University, Denmark Da Wei Zheng

Department of Computer Science, University of Illinois Urbana-Champaign, IL, USA

Abstract

We introduce the contiguous art gallery problem which is to guard the boundary of a simple polygon with a minimum number of guards such that each guard covers exactly one contiguous portion of the boundary. Art gallery problems are often NP-hard. In particular, it is NP-hard to minimize the number of guards to see the boundary of a simple polygon, without the contiguity constraint.

This paper is a merge of three concurrent works [17, 53, 62] each showing that (surprisingly) the contiguous art gallery problem is solvable in polynomial time. The common idea of all three approaches is developing a greedy function that maps a point on the boundary to the furthest point on the boundary so that the contiguous interval along the boundary between them could be guarded by one guard. Repeatedly applying this function immediately leads to an OPT $+1$ approximation. By studying this greedy algorithm, we present three different approaches that achieve an optimal solution. The first and second approach apply this greedy algorithm from different points on the boundary that could be found in advance or on the fly while traversing along the boundary (respectively). The third approach represents this function as a piecewise linear rational function, which can be reduced to an abstract arc cover problem involving infinite families of arcs. We identify other problems that can be represented by similar functions, and solve them via the third approach.

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.

Keywords and phrases:

Art Gallery Problem, Computational Geometry, Combinatorics, Discrete Algorithms

Funding:

Ahmad Biniaz: Research supported in part by NSERC.

Anil Maheshwari: Research supported in part by NSERC.

Magnus Christian Ring Merrild: Research supported by Independent Research Fund Denmark (DFF), grant 10.46540/3103-00334B.

Joseph S. B. Mitchell: Partially supported by the National Science Foundation (CCF-2007275).

Saeed Odak: Research supported by NSERC.

Valentin Polishchuk: Partially supported by the Swedish Transport Administration and the Swedish Research Council.

Casper Moldrup Rysgaard: Research supported by Independent Research Fund Denmark (DFF), grant 9131-00113B.

Jens Kristian Refsgaard Schou: Research supported by Independent Research Fund Denmark (DFF), grant 9131-00113B.

Thomas Shermer: Research supported by NSERC.

Rolf Svenning: Research supported by Independent Research Fund Denmark (DFF), grant 9131-00113B.

Da Wei Zheng: Research supported in part by an NSERC PGSD.

Copyright and License:

© Ahmad Biniaz, Anil Maheshwari, Magnus Christian Ring Merrild, Joseph S. B. Mitchell,
Saeed Odak, Valentin Polischuk, Eliot W. Robson, Casper Moldrup Rysgaard,
Jens Kristian Refsgaard Schou, Thomas Shermer, Jack Spalding-Jamieson,
Rolf Svenning, and Da Wei Zheng; licensed under Creative Commons License CC-BY 4.0

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Computational geometry

Related Version:

This paper is a merge of 3 submissions: Biniaz, Maheshwari, Mitchell, Odak, Polishchuk, and Shermer: https://arxiv.org/abs/2412.15053 [17]

Merrild, Rysgaard, Schou, and Svenning: https://arxiv.org/abs/2412.13938 [53]

Robson, Spalding-Jamieson, and Zheng: https://arxiv.org/abs/2412.15567 [62]

Supplementary Material:

Software (Source Code): https://github.com/RolfSvenning/ContiguousArtGallery [68]
archived at

swh:1:dir:7cfaba2c09d953feb90a49f0e26370ea3f7719a7

Acknowledgements:

We are grateful to the anonymous reviewers for helpful suggestions, and we thank Joseph O’Rourke for organizing the open problem session at the Canadian Conference on Computational Geometry 2024 (CCCG24), where Thomas C. Shermer proposed the contiguous art gallery problem. The authors further thank the participants of CCCG24 for their lively discussions of the problem at the conference. We thank the members of the Stony Brook CG Group open problem seminar (2022), where Joe Mitchell posed questions regarding a greedy algorithm for the “CBG” (Contiguous Boundary Guarding) problem and its variants.

DOI:

10.4230/LIPIcs.SoCG.2025.20

Event:

41st International Symposium on Computational Geometry (SoCG 2025)

Editors:

Oswin Aichholzer and Haitao Wang

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

The art gallery problem, introduced in 1973 by Victor Klee [20, 58], asks for a minimum number of guards that see every point of a given polygon $P$ – the guards can lie anywhere in the polygon. This problem is central to computational geometry and is an active research area. It is long known to be NP-hard [48] and APX-hard [32]; see also [5, 58, 60]. A recent result by Abrahamsen, Adamaszek, and Miltzow [3, 2] shows that the problem is $\exists\mathbb{R}$ -complete even if the vertices have integer coordinates. In fact, [1] and [52] present instances with optimal solutions of size 3 and 2 that require guards with irrational coordinates. The problem is notoriously difficult, as the best known approximation algorithms have logarithmic approximation factors [18, 27, 30, 31]; see also [32] for hardness of approximation.

The boundary guarding problem is a variant of the art gallery problem in which the goal is to guard only the boundary of $P$ with a minimum number of guards that can lie anywhere in $P$ . One may think of this as guarding only the walls of an art gallery, with no interior sculptures. By extending ideas of [3, 2], Stade has shown that this variant is also $\exists\mathbb{R}$ -complete [67]. In this paper we introduce the contiguous version of this problem. In the contiguous art gallery problem, the goal is to guard the boundary of $P$ such that each guard covers a contiguous portion of the boundary. While the visibility polygon of a guard may have several connected components on the boundary, the guard is assigned to only one component.

The contiguous art gallery problem is a natural modification of the boundary guarding problem: Here, the responsibility of a guard is a part of the boundary that could be contiguously scanned by a rotating security camera (or human) that cannot pause its rotation to completely re-focus (or perform an autofocus). The problem appeared in open problems from CCCG 2024 [8], motivated by the fact that the hardness proofs for typical art gallery variants [3, 2, 67] require guards to cover several connected components on the boundary. Figure 1 illustrates the difference between standard boundary guarding and the contiguous version. In this paper, we give polynomial-time algorithms for contiguous boundary guarding.

We present three approaches to the problem. All three start from the observation that there is a function $\operatorname{\textsc{G}}$ called the greedy function, mapping points along the boundary of the polygon to maximal point counterclockwise along the boundary so that a guard point exists that can guard the entire boundary between the two points. We discuss this function in Section 1.4, including how it can be used to obtain an additive $+1$ approximation. At a high-level, the three different approaches extend this in different manners: The first applies $\operatorname{\textsc{G}}$ repeatedly until it produces an optimal solution, going around the polygon a polynomial number of times. The second studies the specific structure of an optimal solution, showing that a polynomial-sized finite subset of the domain of $\operatorname{\textsc{G}}$ needs to be considered. The third shows that $\operatorname{\textsc{G}}$ has a representation as a piecewise linear rational function, which can be reduced to an abstract arc cover problem involving infinite families of arcs, resulting in the analytic arc cover problem. This third approach can also be applied to solve minimum polygon separation (see Figure 2) and polytope carving (see Figure 3) in polynomial time.

Figure 1: (Left) 3 optimal boundary-covering guards (the interior gray triangle is not seen). (Right) 6 guards that optimally contiguously cover the boundary. Guards are visualized as points whose color matches the boundary portion they guard.

Figure 2: (Left) An instance of the segment separation problem, which asks for a convex polygon with the fewest vertices that separates two input sets of line segments. (Middle) A suboptimal solution. (Right) One possible optimal solution.

Figure 3: The polytope half-plane carving problem asks for the minimum number of half-plane cuts needed to separate a specific target polytope from the ambient material. Pictured is a polytope that can be carved by

10

half-plane cuts.

1.1 Related work and results

The art gallery problem and its variants have been extensively studied. Variants arise from constraints on the allowable input polygon, the allowable guard locations, and the portion of the polygon that must be guarded. Essentially all nontrivial variants are NP-hard.

Hardness and approximations.

The vertex-guard problem requires guards to be at vertices of the polygon. This version is also NP-hard [48, 60] and APX-hard [32] with known logarithmic factor [37] and sub-logarithmic factor [43] approximation algorithms. A similar sub-logarithmic approximation is known for the case where the guards can lie anywhere on the boundary of the polygon [43]. Better approximation algorithms are known for monotone polygons [46] and weakly-visible polygons [11, 12, 14].

Terrain guarding is a related problem in which we are given a 1.5-dimensional terrain (i.e., an $x$ -monotone polygonal chain), and we want to guard the terrain with a minimum number of guards on the terrain – this is a variant of the boundary guarding problem. This problem is also NP-hard [19, 45, 44], and admits a polynomial time approximation scheme [11, 12, 38].

Both versions of the problem (point-guard and vertex-guard) remain NP-hard in orthogonal polygons [65], even if we want to guard only the vertices of the polygon [42].

Polynomial-time exact algorithms.

For some trivial versions, the art gallery problem can be solved in polynomial time, such as for convex, star-shaped, and spiral polygons. Finding non-trivial instances that admit polynomial-time algorithms is of particular interest. To the best of our knowledge, there are only a few such versions. These instances usually enforce constraints on the polygon itself or on the definition of visibility. For example, the authors in [21] present polynomial-time algorithms when the polygon is uni-monotone (i.e., it is monotone and one of its two monotone polygonal chains is a straight line segment)¹¹1This type of polygons are also referred to as monotone mountains. and for 1.5-dimensional terrains where all the guards must be placed on a horizontal line above the terrain. The art gallery problem can also be solved in polynomial time on orthogonal polygons under rectilinear visibility [76] and staircase visibility [56, 55]. In the former case, two points are visible if their minimum orthogonal bounding box lies in the polygon, and in the latter case, two points are visible if there is an $x$ - and $y$ -monotone path between them in the polygon. All of these algorithms [21, 56, 55, 76] employ the notion of perfectness [9, 10] of $P$ , which means that the minimum number of guards is equal to the maximum number of points that can be placed in $P$ such that their visibility polygons are pairwise disjoint.

Combinatorial bounds.

While most variants of the art gallery problem are algorithmically hard, tight combinatorial bounds are known on the numbers of guards that are always sufficient and sometimes necessary to guard a polygon with $n$ vertices. For the original art gallery problem the bound is $\lfloor n/3\rfloor$ for both point-guards and vertex-guards [20, 35], and it is $\lfloor n/4\rfloor$ for orthogonal polygons [40, 50, 64, 74]. Tight bounds are also known for variants in which an entire edge or diagonal can serve as a guard [15, 57, 66].

Contiguity.

The contiguous guarding is particularly related to guarding polygons with cameras/guards that have a bounded field of view (i.e., the maximum angle a camera can cover is limited) [71, 72] and to the so-called floodlight [59, 73] and city guarding problems [13, 16, 24]. It is also related to contiguous guarding of points on a 1.5-dimensional terrain by placing at most $k$ watchtowers such that each watchtower sees a contiguous sequence of points [41].

Circle-cover minimization.

When partitioning the boundary of a simple polygon, it is natural to view it as a circle and the polygonal chains as arcs or intervals; see Figure 4. By doing so, finding a minimal partition is similar to finding a minimal circle-cover among a set of intervals $C$ . This problem was studied by Lee and Lee [47] for finite cardinality $C$ , giving an algorithm that runs in $\mathcal{O}\!\left(\left|C\right|\log{\left|C\right|}\right)$ time. Thus, given a finite set $C$ of polygon chains of the boundary of $P$ such that an optimal solution is contained in $C$ , the problem can be solved in $\mathcal{O}\!\left(\left|C\right|\log{\left|C\right|}\right)$ time, see Figure 4. However, it is not easy to define a set $C$ that is guaranteed to contain an optimal solution.

Minimum Polygon Separation.

Given a convex polygon $P$ contained inside another convex polygon $Q$ , the minimum polygon separation problem asks for a polygon $S$ with the minimum number of vertices such that $S$ contains $P$ and is contained within $Q$ . This is the polygon separation problem. Polygon separation was first studied by Aggarwal, Booth, O’Rourke, Suri, and Yap [6, 7], and generalized to multiple connected domains by Mitchell and Suri [54]. One can consider a similar problem: The problem of separating two collections of line segments by a polygon with the minimum number of vertices. This is the segment separation problem.

Polytope Carving.

Related to polygon separation is the problem of carving one shape out of another, or out of an ambient space. Two-dimensional carving was first studied by Overmars and Welzl [61], where they aimed to find the cheapest sequence of line cuts to carve a convex polygon out of a piece of flat material. This has also been studied in the context of rays cuts [22, 23, 69] and line segments cuts [25, 26, 28, 29], as well as in 3D with half-plane cuts [63].

1.2 Preliminaries

Let $P$ be a simple polygon with $n$ vertices. We denote the boundary of $P$ by $\partial P$ . A reflex vertex of $P$ is a vertex with an interior angle greater than $\pi$ . A non-reflex vertex is a convex vertex. For two points $p$ and $q$ in the plane, we denote by $\overline{p\,q}$ the straight line segment between $p$ and $q$ . The ray from $p$ toward $q$ is denoted $\overrightarrow{p\,q}$ . A wedge is a region of the plane bounded by two rays starting from the same point known as the apex of the wedge.

We assume that $\partial P$ is a directed cycle, with vertices ordered counter-clockwise. We index the edges $e_{i}$ and the vertices $v_{i}$ of $P$ modulo $n$ , that is, $e_{n}=e_{0}$ and $v_{n}=v_{0}$ . We define a polygonal chain as a connected portion of $\partial P$ . For an ordered pair $(p_{1},p_{2})$ of two points on $\partial P$ , we denote by $[p_{1},p_{2}]$ the interval of $\partial P$ from $p_{1}$ to $p_{2}$ in counter-clockwise direction – $[p_{1},p_{2}]$ is a directed path, see Figure 4. We refer to $p_{1}$ and $p_{2}$ as the first and the last endpoints of $[p_{1},p_{2}]$ , respectively. Since $[p_{1},p_{2}]$ is directed, for any two points $p$ and $q$ on $[p_{1},p_{2}]$ , we can tell if $p$ appears before or after $q$ . We define a guardable interval $[p_{1},p_{2}]$ to be one for which there exists a point $g\in P$ (guard) such that for all $x\in[p_{1},p_{2}]$ we have $\overline{x\,g}\subset P$ . Now, a contiguous boundary guarding (CBG) is a collection of guards $\Gamma=\{g_{i}\}_{i}$ with guardable intervals $\partial(g_{i})=[a_{i},b_{i}]$ such that $\cup_{i}\partial(g_{i})=\partial P$ . Multiple guards could be collocated ( $g_{i}=g_{j}$ ) while guarding different intervals ( $\partial(g_{i})\neq\partial(g_{j})$ ). We say that $\Gamma$ is minimal if the removal of any guard from $\Gamma$ results in an uncovered portion of $\partial P$ . The goal of the contiguous art gallery problem is to find a smallest minimal guarding, and we define ${k^{*}}$ to be the size of such a guarding.

Figure 4: A simple polygon visualized as a circle, with intervals of the polygonal boundary represented as arcs on the circle.

Let $p_{1}(g)$ and $p_{2}(g)$ denote the first and last endpoints of $\partial(g)$ . We denote by $w(g)$ the wedge from the ray $\overrightarrow{g\,p_{1}(g)}$ to the ray $\overrightarrow{g\,p_{2}(g)}$ intersected with $P$ , see Figure 5. Further note that for every guard $g$ in a minimal contiguous guarding, there exists a point $g_{p}$ of $\partial P$ that is guarded by $g$ alone, because otherwise we could remove $g$ from the guard set. For any (minimal) contiguous guarding $\Gamma$ , the counter-clockwise order of $\{g_{p}:g\in\Gamma\}$ along $\partial P$ induces an order of the guards in $\Gamma$ . Thus, the terms previous guard, next guard, and consecutive guards are well defined. The following simple observation is valid for any guarding with at least two guards.

Observation 1.

Let $g$ be a guard in a guarding of $\partial P$ . Then, the first endpoint of $\partial(g)$ is covered by $g$ and by the previous guard. Similarly, the last endpoint of $\partial(g)$ is covered by $g$ and the next guard.

Figure 5: The boundary of the polygon is assumed to be directed counter-clockwise.

1.3 Combinatorial Bounds

In this section, we determine the number of guards that are always sufficient and sometimes necessary to guard an $n$ -vertex polygon. It is easily seen that a chain with $n$ edges can be covered by $\lfloor\frac{n+1}{2}\rfloor$ guards – this can be achieved by placing a guard at every second vertex. Thus it follows that a polygon with $n$ vertices (and hence $n$ edges) can be covered by $\lfloor\frac{n+1}{2}\rfloor$ guards. As we will see later, this bound is very close to the best achievable bound but is not tight. We need stronger ingredients, such as the following lemma, to obtain a tight bound. In this section we say that a vertex “covers” an edge if the vertex sees both endpoints.

Lemma 2.

For any polygon $P$ with at least $8$ vertices, one of the following statements holds.

1.

There is a vertex that covers $6$ consecutive edges of $\partial P$ .
2.

There are two vertices that collectively cover $7$ consecutive edges of $\partial P$ .
3.

There are two vertices that collectively cover $8$ edges of $\partial P$ such that each vertex covers $4$ consecutive edges.

Theorem 3.

In any polygon $P$ with $n\geq 4$ vertices there exists a set of at most $\lfloor\frac{n-2}{2}\rfloor$ points that guard the boundary of $P$ contiguously. This bound is tight.

Proof.

If $n=4,5$ , then one vertex of the polygon covers the entire boundary (to verify this, observe that in any triangulation of a $5$ -gon, there is a vertex that is incident to the three resulting triangles). If $n=6$ , then any triangulation contains a diagonal that partitions the boundary of $P$ into 2 and 4 consecutive edges;²²2For any $k\geq 2$ there is a diagonal that cuts off at least $k$ and at most $2k{-}2$ edges of the polygon; see [15]. each partite can be covered by one vertex. If $n=7$ , then there is a diagonal that partitions the boundary of $P$ into 3 and 4 consecutive edges; again, each partite can be covered by one vertex.

Assume that $n\geq 8$ . Then, at least one of the cases in Lemma 2 holds. For each case, we show how to cover $\partial P$ by the number of guards that is claimed.

$\blacksquare$

Statement 1 holds. We cover $6$ consecutive edges by $1$ guard and the remaining chain of $n{-}6$ edges by at most $\lfloor\frac{n-5}{2}\rfloor$ guards. Thus, the total number of guards is at most $\lfloor\frac{n-3}{2}\rfloor$ .
$\blacksquare$

Statement 2 holds. We cover $7$ consecutive edges by $2$ guards and the remaining chain of $n{-}7$ edges by at most $\lfloor\frac{n-6}{2}\rfloor$ guards. The total number of guards is at most $\lfloor\frac{n-2}{2}\rfloor$ .
$\blacksquare$

Statement 3 holds. We cover the $8$ edges by two guards. If $8$ edges are consecutive, then we cover the remaining chain as in the previous case. Assume they are not consecutive and thus split into two sets, each having four consecutive edges. The remaining $n{-}8$ edges of $\partial P$ form two disjoint chains of $n_{1}$ and $n_{2}$ edges that can be covered by at most $\lfloor\frac{n_{1}+1}{2}\rfloor$ and $\lfloor\frac{n_{2}+1}{2}\rfloor$ guards, respectively. The total number of guards is at most $\lfloor\frac{n_{1}+1}{2}\rfloor+\lfloor\frac{n_{2}+1}{2}\rfloor+2\leq\frac{n-2% }{2}$ . This equals $\lfloor\frac{n-2}{2}\rfloor$ when $n$ is even. When $n$ is odd, one of the chain sizes, say $n_{1}$ , is even, and hence the chain itself can be covered by at most $\lfloor\frac{n_{1}}{2}\rfloor$ guards, which would result in at most $\frac{n-3}{2}\leq\lfloor\frac{n-2}{2}\rfloor$ total guards.

Figure 6: Illustration of the lower bound

\lfloor\frac{n-2}{2}\rfloor

guards. The polygonal arcs around the boundary are maximal chains that can each be guarded by a single guard.

To verify the lower bound, see the polygon in Figure 6 of size $n=4k+2$ , for some integer $k$ , which consists of two convex chains of odd length $\frac{n}{2}$ . We need at least $2\lfloor\frac{n/2+1}{2}\rfloor-2=\lfloor\frac{n-2}{2}\rfloor$ guards to cover the boundary of this polygon contiguously. By adding a vertex on any edge of the polygon in Figure 6, a lower bound example for odd $n$ is obtained. $\hfill\blacktriangleleft$

1.4 Greedy Steps

Our overall approach to solving the contiguous art gallery problem studied in this paper is based on the idea to take a point $x\in\partial P$ and find the furthest counter clockwise point $\operatorname{\textsc{G}}(x)\in\partial P$ such that $[x,\operatorname{\textsc{G}}(x)]$ is guardable. We introduce the GreedyInterval algorithm that given $x$ on edge $e_{i-1}=\overline{v_{i-1}\,v_{i}}$ computes $\operatorname{\textsc{G}}(x)$ progressively by intersecting the visibility polygons (V) of vertices $v_{i},\dots,v_{i+j}$ such that the feasible region $F_{j}:=\cap_{h=0}^{j}V\hskip-1.99997pt\left(P,v_{i+h}\right)\neq\emptyset$ and $F_{j+1}=\emptyset$ , then the feasible region can be used to compute the maximal point $\operatorname{\textsc{G}}(x)$ on edge $e_{i+j}=\overline{v_{i+j}\,v_{i+j+1}}$ such that a guard can be placed in $P$ that can see from $x$ to $\operatorname{\textsc{G}}(x)$ , here maximality means that $\operatorname{\textsc{G}}(x)$ is closest possible to $v_{i+j+1}$ on $\partial P$ such that $[x,\operatorname{\textsc{G}}(x)]$ is guardable.

Lemma 4.

The GreedyInterval algorithm can be computed in $\mathcal{O}\!\left(jn\log n\right)$ arithmetic operations using poly $(n)$ bits on $x\in\partial P$ where $j$ is the number of vertices in $[x,\operatorname{\textsc{G}}(x)]$ .

Proof Sketch.

Visibility polygons can be computed in $\mathcal{O}\!\left(n\right)$ by an algorithm of Gindy and Avis [33]. The number of vertices of the feasible region can be shown to be $\mathcal{O}\!\left(n\right)$ , independent of $j$ . An algorithm by Martínez, Rueda, and Feito [51] shows that the intersections can be computed in $\mathcal{O}\!\left((n_{1}+n_{2}+h)\log(n_{1}+n_{2})\right)$ time which together implies that the final feasible region can be computed in $\mathcal{O}\!\left(jn\log n\right)$ time. Finally, to compute how far along edge $\overline{v_{i+j}\,v_{i+j+1}}$ $\operatorname{\textsc{G}}(x)$ can be placed, we construct a new blocking polygon from following the rightmost tangent of $F_{j}$ through $v_{i+j+1}$ and the pieces of $\partial P$ that stick below this tangent. If this would touch $F_{j}$ , we instead connect it to a point $r$ above the tangent and finish the construction by connecting this back to $v_{i+j+1}$ . Now, $\operatorname{\textsc{G}}(x)$ can be computed using a common tangent between $F_{j}$ and the blocking polygon. This common tangent can be computed with an algorithm of Abrahamsen and Walczak [4]. This process takes $\mathcal{O}\!\left(n\log n\right)$ time, so in total, we use $\mathcal{O}\!\left(jn\log n\right)$ time to compute $\operatorname{\textsc{G}}(x)$ . The algorithm is illustrated in Figure 7. $\hfill\blacktriangleleft$

Figure 7: The steps of the GreedyInterval algorithm animated. First successive iterations of computing visibility polygons (in gray) and intersecting with previous feasible regions (in green) and finally computing the blocking polygon (in blue), to find

\operatorname{\textsc{G}}(x)

through a common tangent.

The GreedyRevolution algorithm starts at some point $x_{0}$ on the boundary and computes a sequence $x_{i+1}=\operatorname{\textsc{G}}(x_{i})$ until $x_{k}$ is between $x_{0}$ and $x_{1}$ .

Theorem 5.

The GreedyRevolution algorithm, starting from an arbitrary point $x\in\partial P$ , returns a guarding $\Gamma$ of size at most ${k^{*}}{+}1$ in $\mathcal{O}\!\left(n^{2}\log n\right)$ arithmetic operations. Moreover, if $x$ is covered by two guards in some optimal solution, then $|\Gamma|={k^{*}}$ .

There is a natural trade-off when guards are moved a little which motivates that it is indeed difficult to check if a candidate solution is optimal or not, see Figure 8.

Figure 8: A polygon where the blue guard

g_{r}

sees all of

r

and none of

\ell

, and vice-versa for

g_{\ell}

. Any guard placed along

s

will yield a trade-off between how much of

\ell

and

r

it sees.

In the remainder of this paper, we present three approaches to proving that the contiguous art gallery problem can be solved using GreedyRevolution in polynomial time.

Theorem 6.

The contiguous art gallery problem is a member of the complexity class P, with a runtime of $\mathcal{O}\!\left(n^{5}k^{*}\log n\right)$

1.5 Organization

This paper is the combination of three independent studies [17, 53, 62] of the contiguous art gallery problem. In Section 2 we show that if we continue applying GreedyRevolution $\mathcal{O}\!\left(n^{3}{k^{*}}\right)$ times then the last candidate solution will be optimal. In Section 3 we show that generating $\mathcal{O}\!\left(n^{4}\right)$ candidate solutions by starting GreedyRevolution from a carefully selected set of points, at least one of these will be optimal. Finally, in Section 4 we explore how GreedyInterval can be expressed as a piecewise linear rational function and show that repeatedly composing GreedyInterval with itself leads to a piecewise linear rational function representing all optimal solutions.

2 Finding an Optimal Solution via Repeated GreedyRevolution

The approach of Merrild, Rysgaard, Schou and Svenning [53] to solve the contiguous art gallery problem is to define the infinite greedy sequence $(x_{i})_{i=0}^{\infty}$ with $x_{0}=x$ and $x_{i}=\operatorname{\textsc{G}}(x_{i-1})$ and prove that after at most $\mathcal{O}\!\left(n^{3}{k^{*}}\right)$ revolutions the sequence has converged to an optimal solution, leading to $\mathcal{O}\!\left(n^{5}{k^{*}}\log n\right)$ runtime.

2.1 Combinatorial optimality conditions

We initially study finite greedy sequences that do not contain optimal solutions to the contiguous art gallery problem, which we define as non-optimal greedy sequences.

If $P$ is star-shaped, i.e., one guard can see all of $P$ and thus all of $\partial P$ we will be guarded after one call to GreedyInterval. Thus, we assume that this is not the case. This together with some elementary properties of $\operatorname{\textsc{G}}$ and guardable intervals gives the following lemma, which acts like combinatorial axioms:

Lemma 7 (Properties of $\operatorname{\textsc{G}}$ and guardable intervals).

Let $x, y, z, w$ be points on $\partial P$ .

1.

$\operatorname{\textsc{G}}(x)\neq x$ .
2.

If $[x,y]\subseteq[z,w]$ and $[z,w]$ is guardable then $[x,y]$ is guardable.
3.

$[x,y]\subseteq[x,\operatorname{\textsc{G}}(x)]$ if and only if $[x,y]$ is guardable.

Using these properties, we derive the following

Proposition 8 (Behavior of non-optimal greedy sequences).

Let $x\in\partial P$ and assume that the finite greedy sequence $(x_{i})_{i=0}^{k\cdot N}$ starting at $x$ does not contain an optimal solution to the ContiguousArtGallery problem, where $k$ is the length of a revolution and $N$ is some positive integer. Let $y_{0},y_{1},\dots,y_{{k^{*}}-1}$ be an optimal solution with $y_{0}\in(x_{0},x_{1}]$ . Then $x_{ik+m}\in[y_{m-1},x_{(i-1)k+m})$ for all $m\in\{1,\dots,k\}$ and $i\in\{1,2,\dots,N-1\}$ .

The proof of this proposition follows from considering the greedy steps performed and bounding the result with previous greedy endpoints and optimal endpoints, see Figure 9.

Figure 9: For a non-optimal greedy sequence

\operatorname{\textsc{G}}

maps points from

[y_{0},x_{2k+1}]

(green) to

[y_{1},x_{2k+2}]

(orange), and in the next revolution from

[y_{0},x_{3k+1}]

to

[y_{1},x_{3k+2}]

.

From this we see that the subsequence $x_{1},x_{k+1},x_{2k+1},...$ must be in the interval $[y_{0},y_{1}]$ and the endpoints get closer and closer to $y_{0}$ . Likewise, all subsequences $x_{m},x_{k+m},x_{2k+m},...$ lie in $[y_{m-1},y_{m}]$ and approach $y_{m-1}$ . Thus, we give these subsequences a name:

Definition 9 (Local Greedy Sequence).

Let $x\in\partial P$ , consider the greedy sequence $(x_{i})_{i=0}^{\infty}$ starting at $x$ . Then $(x_{i}^{m})_{i=0}^{\infty}$ for $m=1,\dots,k$ are local greedy sequences, where $x_{i}^{m}=x_{ik+m}$ .

Now, any greedy sequence that does not look like those classified in Proposition 8 must contain an optimal solution. The next step of our analysis is to study geometric polygonal patterns that lead to deviations from this.

2.2 Achieving optimality conditions using Geometry

We now define patterns in which progress toward an optimal solution is achieved:

Definition 10 (Fingerprint).

Let $(x_{i}^{m})_{i=0}^{\infty}$ be the $m$ ’th local greedy sequence. For $i\geq 1$ we say that $x_{i}^{m}$ has a negative fingerprint if $x_{i}^{m}\in[x_{m-1},x_{i-1}^{m})$ . Otherwise, we say that $x_{i}^{m}$ has a positive fingerprint.

Definition 11 (Edge jumps).

Let $(x_{i}^{m})_{i=0}^{\infty}$ be the $m$ ’th local greedy sequence. We say that $(x_{i}^{m})_{i=0}^{\infty}$ has an edge jump at $i$ if $x_{i}^{m}$ is a vertex of $P$ or $x_{i}^{m}$ and $x_{i+1}^{m}$ are on different edges of $P$ and neither is a vertex of $P$ .

By comparing these with Proposition 8, we get the following optimality conditions:

Lemma 12 (Progress conditions).

If any of the following three conditions are met, the greedy sequence will contain an optimal solution to the ContiguousArtGallery problem:

1.

If there is a positive fingerprint.
2.

If there is repetition in the greedy sequence.
3.

If there are $n+1$ edge jumps.

Thus, the intermediate goal is to prove the following:

Theorem 13 (GreedyRevolution will reach a progress condition).

Running GreedyRevolution $\mathcal{O}\!\left({k^{*}}n^{2}\right)$ times guarantees the appearance of a progress condition.

We show the theorem by zooming in on one greedy step from one local greedy sequence to another. We let $(y_{i})_{i=0}^{\infty}$ and $(z_{i})_{i=0}^{\infty}$ be two local greedy sequences such that $z_{i}=\operatorname{\textsc{G}}(y_{i})$ .

Figure 10: A greedy step from

y_{i}

to

z_{i}:=\operatorname{\textsc{G}}(y_{i})

guarded by

g_{i}

. The pivot point

C_{z,i}

blocks

g_{i}

from seeing further than

z_{i}

and the other pivot

C_{y,i}

blocks

g_{i}

in the other direction. The relative position of the line

\ell_{i}:=L(C_{z,i},C_{y,i})

between pivot points to

g_{i}

is essential for the casework.

We denote the guard, which can see $[y_{i},z_{i}]$ by $g_{i}$ and let $C_{z,i}$ and $C_{y,i}$ be the vertices of $P$ that block $g_{i}$ from seeing more than, respectively $z_{i}$ and $y_{i}$ on $\partial P$ , see Figure 10. We define these vertices as pivot points. We let $\ell_{i}$ be the line through $C_{y,i}$ and $C_{z,i}$ . We define this line as the pivot line and consider the cases where $g_{i}$ lies above or below $\ell_{i}$ .

If $g_{i}$ is above $\ell_{i}$ , we define the shadow $S(a)$ of a point $a$ as the region bounded by the lines $L(C_{y,i},a)$ and $L(C_{z,i},a)$ and above $a$ , see Figure 11. If we let $F$ denote the feasible region of the vertices of $\partial P$ between $y_{i}$ and $z_{i}$ , one gets the following:

Lemma 14 (The feasible region is contained in the shadow).

Assume that $F$ lies above $\ell_{i}$ and let $a$ be a vertex of $F$ closest to $\ell_{i}$ . Then $F\subseteq S(a)$ .

Figure 11: Placing a guard in the shadow

S(a)

of

a

leads to a worse guard.

That is, when $F$ lies above $\ell_{i}$ , there is only one best guard that guards this interval (we do not have the trade-off as in Figure 8). So we have:

Proposition 15 (Feasible region over repeated pivot line implies a progress condition).

If $\ell_{i}=\ell_{j}$ for some $i<j$ and $F$ lies above $\ell_{i}$ , then we get a progress condition.

If the guard $g_{i}$ lies below the pivot line $\ell_{i}$ , we can consider the guard that guards one of the pivot points and get the following result:

Proposition 16 (Guard placed below pivot implies other guard placed strictly above pivot).

Let $g_{i}$ lie below the pivot line, then one of the following will occur:

1.

In the next revolution, we will see a progress condition.
2.

There is some guard $\widehat{g}$ found in the next revolution, which is below its pivot line $\widehat{\ell}$ .

We can now use Proposition 15 and Proposition 16 to prove Theorem 13: There are $\mathcal{O}\!\left({k^{*}}\right)$ greedy steps that take place around $\partial P$ at a time, and each of them has $\mathcal{O}\!\left(n^{2}\right)$ possible pivot lines to consider. Each time we see a guard below a pivot line, it either gives a progress condition or forces another guard to lie above its pivot line. By the pigeonhole principle, after seeing $\mathcal{O}\!\left({k^{*}}n^{2}\right)$ guards above their pivot lines, we must have seen a guard above the same pivot line twice, and Proposition 15 gives that we must have achieved a progress condition.

2.3 Proof of Theorem 6

Proof of Theorem 6.

Running GreedyRevolution for $\mathcal{O}\!\left(kn^{2}\right)=\mathcal{O}\!\left({k^{*}}n^{2}\right)$ revolutions guarantees a progress condition, i.e., a positive fingerprint, a repetition, or an edge jump by Theorem 13. Thus, repeating $n+1$ times guarantees at least one positive fingerprint, at least one repetition, or $n+1$ edge jumps. By Lemma 12 the greedy sequence will contain optimal revolutions. Finally, it can be proven that once an optimal solution appears in the greedy sequence, all subsequent revolutions will also be optimal. This requires $\mathcal{O}\!\left({k^{*}}n^{2}\cdot(n+1)\cdot n^{2}\log n\right)=\mathcal{O}% \!\left(n^{5}{k^{*}}\log n\right)$ arithmetic operations. $\hfill\blacktriangleleft$ An open source implementation using CGAL [34, 36, 39, 70, 75] in C++ is available online [68].

3 Simplifying the Domain of GreedyInterval

In this section we present a polynomial-time exact algorithm for contiguous guarding of the boundary $\partial P$ of a simple polygon $P$ . Recall the notation from Figure 5 in subsection 1.2. We assume that $P$ is not star-shaped, so at least $2$ guards are needed.

Without loss of generality, we assume this maximality property: any guard $g$ covers a maximal contiguous portion of $\partial P$ , i.e., $\partial(g)$ is maximal. This implies the following lemma.

Lemma 17.

Let $g$ be a guard in a guarding of $\partial P$ such that $\partial(g)$ is maximal. Then, each boundary ray of $w(g)$ goes through at least one reflex vertex of $P$ .

Algorithm (in a nutshell).

Our algorithm is fairly simple. It finds a polynomial-size set $S$ of starting points on $\partial P$ such that at least one of the points is covered by two guards in some optimal solution. We execute the greedy algorithm for each point in $S$ and return the smallest guard set over all the points in $S$ . From Theorem 5, it follows that the algorithm returns an optimal solution. The algorithm takes polynomial time because $S$ has a polynomial size, and the greedy algorithm runs in polynomial time.

It remains to compute $S$ . This is the most crucial part of the algorithm. First, we find a polynomial-size point set $Q$ such that at least one guard in some optimal solution lies at a point of $Q$ . For each point $q\in Q$ , we compute a set $S(q)$ of all potential first endpoints of $\partial(q)$ for a guard at $q$ . By Lemma 17, these points are the intersections of $\partial P$ with the rays that start from $q$ and pass through reflex vertices of $P$ . Thus, for every reflex vertex $r$ that is visible from $q$ , we add the first intersection point of the ray $\overrightarrow{qr}$ with $\partial P$ to $S(q)$ . We then define the set $S$ as the union of $S(q)$ over all points $q\in Q$ . The set $S$ has a polynomial size because $|Q|$ and the number of reflex vertices are bounded by polynomials.

Let $g^{*}$ be a guard in an optimal solution $\Gamma^{*}$ that lies at a point $q\in Q$ . Then the first endpoint $f^{*}$ of $\partial(g^{*})$ is in $F(q)$ , and hence in $S$ . By Observation 1, $f^{*}$ is covered by $g^{*}$ and the previous guard in $\Gamma^{*}$ . Therefore, $f^{*}$ is a point in $S$ with our desired property of being covered by two guards in an optimal solution.

Figure 12: Edge-extensions are in red and vertex-extensions are in blue. The points in

Q

are represented by small green disks.

Now it remains to compute $Q$ . For every reflex vertex $r$ of $P$ , extend each edge incident to $r$ inside $P$ until hitting $\partial P$ at some point $x$ ; see Figure 12. We refer to the segment $r x$ as an edge-extension. Add a segment between every two reflex vertices of $P$ that are visible to each other and extend it from both endpoints inside $P$ until hitting $\partial P$ at points $y$ and $z$ . We refer to the segment $y z$ by vertex-extension. An extension is either an edge-extension or a vertex-extension. We define $Q$ as the set containing the following points

$\blacksquare$

all vertices of $P$ ,
$\blacksquare$

all intersection points between extensions and $\partial P$ ,
$\blacksquare$

all intersection points between edge-extensions,
$\blacksquare$

all intersection points between an edge-extension and a vertex-extension.

The following structural lemma shows that $Q$ has our desired property.

Lemma 18.

Some optimal solution has a guard at a point of $Q$ .

If $P$ has $n$ vertices, then $Q$ has $O(n^{3})$ points because there are $O(n)$ edge-extensions and $O(n^{2})$ vertex-extensions. The set $S$ has size $O(n^{4})$ . Recall that the greedy algorithm takes $O(n^{2}\log n)$ time for a given starting point. Therefore, the total running time of the optimal algorithm, which invokes the greedy algorithm from each starting point in $S$ , is $O(n^{6}\log n)$ . This is a conservative upper bound on the running time and surely can be improved. For example, one might adopt ideas from the $O(n)$ -time incremental algorithm for the kernel of a polygon [49] to achieve a better running time for the greedy algorithm. Our main goal here is a proof that the decision version of the contiguous boundary guarding problem is in the complexity class P. The following theorem summarizes our result.

Theorem 19.

The problem of contiguous boundary guarding of a polygon with the minimum number of guards can be solved in polynomial time.

Remark.

One might wonder if Lemma 18 holds for every optimal solution, i.e., whether every optimal solution has a guard in $Q$ . Also, one might wonder whether there always exists an optimal solution in which two guards cover the same vertex of the polygon. If this were true, then running the greedy algorithm from all vertices of the polygon would suffice. However, none of these statements are true as shown in Figure 13. (For the second statement, one can verify that no guard can cover a red cross and a blue cross simultaneously. Therefore, any optimal solution must have a guard in the red triangle and a guard in the blue triangle. Then, the contiguous coverages of such guards do not have any vertex in common.)

Figure 13: An optimal solution, with two guards, none of which is in

Q

. The coverages of no two guards, in any optimal solution, share a vertex of the polygon.

4 The Analytic Arc Cover Problem

The approach of Robson, Spalding-Jamieson, and Zheng [62] for the contiguous art gallery problem was to consider the analytic arc cover problem. This problem is a version of the interval cover problem on a circle with infinite number of intervals. Each interval is described by the counterclockwise segment between two points $a$ and $b$ on the circle $S^{1}$ , denoted by $[a,b]$ . This infinite set of intervals is given implicitly as a function, as can be seen in the following definition.

Definition 20.

Let $\operatorname{\textsc{G}}:S^{1}\to S^{1}$ be a function that maps points on the unit circle $S^{1}$ to other points on the unit circle $S^{1}$ . The analytic arc cover problem asks to find the minimum set $X\subset S^{1}$ such that the set of counter-clockwise arcs $\{[x,\operatorname{\textsc{G}}(x)]:x\in X\}$ covers $S^{1}$ .

Note that we require some additional properties for this problem to be algorithmically solvable and avoid pathalogical examples (e.g. that there exists a finite cover). We leave these details to the full version of this approach [62].

Figure 14: A mapping between parts of the unit circle where the functions

f_{1}

,

f_{2}

, and

f_{3}

are linear rational functions.

We show that the contiguous boundary art gallery problem reduces to analytic arc cover with piecewise linear-rational functions over a unit-interval representation, i.e., the function $\operatorname{\textsc{G}}$ is a piecewise-continuous function that is decomposable into linear rational functions $f_{1},f_{2},\dots,f_{\ell}$ . See Figure 14 for an illustration of this. We crucially use the fact that a compositions of two linear rational functions yields another linear rational function. Using this fact, we show that these instances of the analytic arc cover problem are solvable in polynomial time. In addition, we show that minimizing the number of half-plane cuts to carve a 3D polytope reduces to multiple instances of segment separation. We can conclude that finding the minimum cuts to carve a polytope is also solvable in polynomial time.

Theorem 21.

Minimizing the number of half-plane cuts to carve a 3D polytope is in $\mathsf{P}$ .

4.1 Outline of approach

At a high level, we show that for instances of the analytic arc cover problem where we can compute a greedy function $\operatorname{\textsc{G}}$ that is piecewise linear, then the problem can be solved in polynomial time.

Analytic Arc Cover

We show that the analytic arc cover problem is solvable in polynomial time when the input function $\operatorname{\textsc{G}}$ is a piecewise linear rational function with rational coefficients.

Observation 22.

The following is true of piecewise linear rational functions.

$\blacksquare$

For two piecewise linear rational functions $\operatorname{\textsc{G}}_{1}$ and $\operatorname{\textsc{G}}_{2}$ , where $\operatorname{\textsc{G}}_{1}$ consists of $n_{1}$ pieces and $\operatorname{\textsc{G}}_{2}$ has $n_{2}$ pieces, the composition $\operatorname{\textsc{G}}=\operatorname{\textsc{G}}_{1}\circ\operatorname{% \textsc{G}}_{2}$ is a piecewise linear rational function of $n_{1}+n_{2}$ parts.
$\blacksquare$

For a piecewise linear rational function $\operatorname{\textsc{G}}:S^{1}\to S^{1}$ that consists of $n$ pieces, it is possible to determine if the function “wraps around” in $O(n)$ time.

The formal definition of “wrapping around” the circle is omitted for brevity (this requires lifting to a covering space), and is given in full detail in [63]. Using these observations, it is straightforward to prove the following theorem.

Theorem 23.

Let $\operatorname{\textsc{G}}:S^{1}\to S^{1}$ be a piecewise linear rational function. Let $I^{*}$ be a solution to the analytic arc cover problem that consists of $k$ arcs. Then the analytic arc cover problem on can be solved in $O(nk)$ time.

Proof.

Let $\operatorname{\textsc{G}}^{(j)}$ denote the function $\widetilde{G}$ composed with itself $j$ times, so $\operatorname{\textsc{G}}^{(j)}=\operatorname{\textsc{G}}\circ\operatorname{% \textsc{G}}^{(j-1)}$ . Thus we can compute $\operatorname{\textsc{G}}^{(j)}$ for each $i$ via function compositions. For each $\operatorname{\textsc{G}}^{(j)}$ we can determine if there is a solution of size $j$ , and halt if so. Note that $\operatorname{\textsc{G}}^{(j)}$ is a piecewise linear rational function with $j n$ pieces. This algorithm terminates after $k-1$ function compositions, taking a total of $O(nk)$ time. $\hfill\blacktriangleleft$

Contiguous Art Gallery

We reduce the contiguous art gallery problem to the analytic arc cover problem for the greedy function $\operatorname{\textsc{G}}$ which is piecewise linear rational. (See Figure 8 for an illustration of this).

To prove this (in a constructive manner), we give a series of piecewise linear rational functions mapping an individual “input” segment of the polygon to an “output” segment of the polygon. The final in each series are combined to form one piecewise linear rational function for the entire polygon. Each function in the sequence leverages the last, so that each one incorporates more elements of the problem constraining the final function in various ways. In particular, the constraints that are progressively introduced are:

$\blacksquare$

The input and output segments themselves constraint the possible guard locations.
$\blacksquare$

The segments between the input and output segment must be guarded and thus constrain the possible guard locations.
$\blacksquare$

The portion of the polygon not being guarded constrains the possible guard locations.

In the full version [62], the functions presented in “most-constraining” to “least-constraining” order. At each step, functions for different subsets of constraints can be combined with $\min$ and $\max$ operators, which preserve the piecewise linear rational structure. Some care is needed for this part to ensure that the number of pieces is polynomial, and that the endpoints attained in the algorithm do not have exponential bit complexity.

Polygon Separation and Polytope Carving

Similarly, we can reduce the problem of segment separation, where we wish to separate two sets of line segments to an instance of analytic arc cover with a piecewise rational function. The function is in some sense less complex than the one for the contiguous art gallery problem, in that it requires fewer steps, but we make use of a special case of piecewise linear rational functions over two variables instead of one.

We also show that the problem of determining the minimum number of cuts to cut out a 3D polytope reduces to a polynomial number of instances of segment separation, and hence this problem can also be solved in strongly polynomial time.

5 Future work

In this paper, we have presented an $\mathcal{O}\!\left(n^{5}{k^{*}}\log n\right)$ solution to the contiguous art gallery problem. We believe that the solution using repeated GreedyRevolution can find an optimal solution in as few as $\mathcal{O}\!\left(\operatorname{polylog}n\right)$ revolutions, maybe only constantly many, as our experiments never needed more than four revolutions. Furthermore, we believe that GreedyRevolution can be implemented to run in $\mathcal{O}\!\left(n\log n\right)$ time; we are unsure if, in fact, linear time may be possible. In total, a final runtime of $\mathcal{O}\!\left(n\operatorname{polylog}n\right)$ should be possible. Variants of the contiguous art gallery problem can be considered. For instance, 3D contiguous art gallery problem or higher-dimensional contiguous art gallery problem, or variants where each guard can see at most $m$ contiguous intervals. We believe that all these variants are NP-hard.

References

[1] Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow. Irrational guards are sometimes needed. In Proceedings of the 33rd International Symposium on Computational Geometry (SoCG), pages 3:1–3:15, 2017. doi:10.4230/LIPICS.SOCG.2017.3.
[2] Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow. The art gallery problem is $\exists\mathbb{R}$ -complete. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 65–73. ACM, 2018. doi:10.1145/3188745.3188868.
[3] Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow. The art gallery problem is $\exists\mathbb{R}$ -complete. J. ACM, 69(1):4:1–4:70, 2022. doi:10.1145/3486220.
[4] Mikkel Abrahamsen and Bartosz Walczak. Common tangents of two disjoint polygons in linear time and constant workspace. ACM Trans. Algorithms, 15(1), December 2018. doi:10.1145/3284355.
[5] Alok Aggarwal. The art gallery theorem: its variations, applications and algorithmic aspects. PhD thesis, The Johns Hopkins University, 1984.
[6] Alok Aggarwal, Heather Booth, Joseph O’Rourke, Subhash Suri, and Chee-Keng Yap. Finding minimal convex nested polygons. In Joseph O’Rourke, editor, Proceedings of the First Annual Symposium on Computational Geometry, Baltimore, Maryland, USA, June 5-7, 1985, pages 296–304. ACM, 1985. doi:10.1145/323233.323271.
[7] Alok Aggarwal, Heather Booth, Joseph O’Rourke, Subhash Suri, and Chee-Keng Yap. Finding minimal convex nested polygons. Inf. Comput., 83(1):98–110, 1989. doi:10.1016/0890-5401(89)90049-7.
[8] 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.
[9] Yoav Amit, Joseph S. B. Mitchell, and Eli Packer. Locating guards for visibility coverage of polygons. In Proc. Ninth Workshop on Algorithm Engineering and Experiments, Proceedings in Applied Mathematics, pages 120–134. SIAM, 2007. doi:10.1137/1.9781611972870.12.
[10] Yoav Amit, Joseph S. B. Mitchell, and Eli Packer. Locating guards for visibility coverage of polygons. International Journal of Computational Geometry & Applications, 20(5):601–630, October 2010. doi:10.1142/S0218195910003451.
[11] Stav Ashur, Omrit Filtser, Matthew J. Katz, and Rachel Saban. Terrain-like graphs: Ptass for guarding weakly-visible polygons and terrains. In Evripidis Bampis and Nicole Megow, editors, Approximation and Online Algorithms - 17th International Workshop, WAOA 2019, Munich, Germany, September 12-13, 2019, Revised Selected Papers, volume 11926 of Lecture Notes in Computer Science, pages 1–17. Springer, 2019. doi:10.1007/978-3-030-39479-0_1.
[12] 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.
[13] 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. doi:10.1007/978-3-540-69733-6_59.
[14] 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.
[15] 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.
[16] 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.
[17] Ahmad Biniaz, Anil Maheshwari, Joseph S. B. Mitchell, Saeed Odak, Valentin Polishchuk, and Thomas C. Shermer. Contiguous boundary guarding, 2024. doi:10.48550/arXiv.2412.15053.
[18] Édouard 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.
[19] 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. URL: http://www.cccg.ca/proceedings/1995/cccg1995_0022.pdf.
[20] Vasek Chvátal. A combinatorial theorem in plane geometry. Journal of Combinatorial Theory, Series B, 18(1):39–41, 1975.
[21] 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.
[22] Ovidiu Daescu and Jun Luo. Cutting out polygons with lines and rays. In Rudolf Fleischer and Gerhard Trippen, editors, Algorithms and Computation, 15th International Symposium, ISAAC 2004, Hong Kong, China, December 20-22, 2004, Proceedings, volume 3341 of Lecture Notes in Computer Science, pages 669–680. Springer, 2004. doi:10.1007/978-3-540-30551-4_58.
[23] Ovidiu Daescu and Jun Luo. Cutting out polygons with lines and rays. Int. J. Comput. Geom. Appl., 16(2-3):227–248, 2006. doi:10.1142/S0218195906002014.
[24] 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.
[25] Erik D. Demaine, Martin L. Demaine, and Craig S. Kaplan. Polygons cuttable by a circular saw. In Proceedings of the 12th Canadian Conference on Computational Geometry, Fredericton, New Brunswick, Canada, August 16-19, 2000, 2000. URL: http://www.cccg.ca/proceedings/2000/36.ps.gz.
[26] Erik D. Demaine, Martin L. Demaine, and Craig S. Kaplan. Polygons cuttable by a circular saw. Comput. Geom., 20(1-2):69–84, 2001. doi:10.1016/S0925-7721(01)00036-0.
[27] 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. doi:10.1007/978-3-540-73951-7_15.
[28] Adrian Dumitrescu and Masud Hasan. Cutting out polygons with a circular saw. In Takao Asano, Shin-Ichi Nakano, Yoshio Okamoto, and Osamu Watanabe, editors, Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Yokohama, Japan, December 5-8, 2011. Proceedings, volume 7074 of Lecture Notes in Computer Science, pages 230–239. Springer, 2011. doi:10.1007/978-3-642-25591-5_25.
[29] Adrian Dumitrescu and Masud Hasan. Cutting out polygons with a circular saw. Int. J. Comput. Geom. Appl., 23(2):127–140, 2013. doi:10.1142/S0218195913600030.
[30] Alon Efrat and Sariel Har-Peled. Guarding galleries and terrains. In Ricardo A. Baeza-Yates, Ugo Montanari, and Nicola Santoro, editors, Foundations of Information Technology in the Era of Networking and Mobile Computing, IFIP 17 ${}^{\mbox{th}}$ World Computer Congress - TC1 Stream / 2 ${}^{\mbox{nd}}$ IFIP International Conference on Theoretical Computer Science (TCS 2002), August 25-30, 2002, Montréal, Québec, Canada, volume 223 of IFIP Conference Proceedings, pages 181–192. Kluwer, 2002. doi:10.1007/978-0-387-35608-2_16.
[31] 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.
[32] Stephan J. Eidenbenz, Christoph Stamm, and Peter Widmayer. Inapproximability results for guarding polygons and terrains. Algorithmica, 31(1):79–113, 2001. doi:10.1007/S00453-001-0040-8.
[33] 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. doi:10.1016/0196-6774(81)90019-5.
[34] Andreas Fabri, Geert-Jan Giezeman, Lutz Kettner, Stefan Schirra, and Sven Schönherr. On the design of cgal a computational geometry algorithms library. Software: Practice and Experience, 30(11):1167–1202, 2000. doi:10.1002/1097-024X(200009)30:11\%3C1167::AID-SPE337\%3E3.0.CO;2-B.
[35] Steve Fisk. A short proof of chvátal’s watchman theorem. Journal of Combinatorial Theory, Series B, 24(3):374, 1978. doi:10.1016/0095-8956(78)90059-X.
[36] 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.
[37] 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.
[38] 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.
[39] 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.
[40] Jeff Kahn, Maria Klawe, and Daniel Kleitman. Traditional galleries require fewer watchmen. SIAM Journal on Algebraic Discrete Methods, 4(2):194–206, 1983.
[41] 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.
[42] 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.
[43] James King and David G. Kirkpatrick. Improved approximation for guarding simple galleries from the perimeter. Discret. Comput. Geom., 46(2):252–269, 2011. doi:10.1007/S00454-011-9352-X.
[44] James King and Erik Krohn. Terrain guarding is np-hard. In Moses Charikar, editor, Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 1580–1593. SIAM, 2010. doi:10.1137/1.9781611973075.128.
[45] James King and Erik Krohn. Terrain guarding is NP-hard. SIAM J. Comput., 40(5):1316–1339, 2011. doi:10.1137/100791506.
[46] 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.
[47] C.C. Lee and D.T. Lee. On a circle-cover minimization problem. Information Processing Letters, 18(2):109–115, 1984. doi:10.1016/0020-0190(84)90033-4.
[48] 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.
[49] 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.
[50] 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.
[51] 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. doi:10.1016/j.cageo.2008.08.009.
[52] Lucas Meijer and Tillmann Miltzow. Sometimes two irrational guards are needed. ArXiv, abs/2212.01211, 2022. doi:10.48550/arXiv.2212.01211.
[53] 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. doi:10.48550/arXiv.2412.13938.
[54] Joseph S. B. Mitchell and Subhash Suri. Separation and approximation of polyhedral objects. In Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’92, pages 296–306, USA, 1992. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=139404.139467.
[55] Rajeev Motwani, Arvind Raghunathan, and Huzur Saran. Covering orthogonal polygons with star polygons: The perfect graph approach. In Herbert Edelsbrunner, editor, Proceedings of the Fourth Annual Symposium on Computational Geometry, Urbana-Champaign, IL, USA, June 6-8, 1988, pages 211–223. ACM, 1988. doi:10.1145/73393.73415.
[56] 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. doi:10.1016/0022-0000(90)90017-F.
[57] Joseph O’Rourke. Galleries need fewer mobile guards: A variation on Chvátal’s theorem. Geometriae Dedicata, 14:273–283, 1983.
[58] Joseph O’Rourke. Art Gallery Theorems and Algorithms. Oxford University Press, 1987.
[59] 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. URL: http://www.cccg.ca/proceedings/1995/cccg1995_0025.pdf.
[60] 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.
[61] Mark H. Overmars and Emo Welzl. The complexity of cutting paper (extended abstract). In Proceedings of the First Annual Symposium on Computational Geometry, Baltimore, Maryland, USA, June 5-7, 1985, pages 316–321. ACM, 1985. doi:10.1145/323233.323274.
[62] 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. doi:10.48550/arXiv.2412.15567.
[63] Eliot W. Robson, Jack Spalding-Jamieson, and Da Wei Zheng. Carving polytopes with saws in 3d. In Rahnuma Islam Nisha, editor, Proceedings of the 36th Canadian Conference on Computational Geometry, CCCG 2024, Brock University, St. Catharines, Ontario, Canada, July 17 - August 19, 2024, pages 145–152, 2024.
[64] Jörg-Rüdiger Sack and Godfried T. Toussaint. Guard placement in rectilinear polygons. In Machine Intelligence and Pattern Recognition, volume 6, pages 153–175. Elsevier, 1988.
[65] 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.
[66] Thomas C Shermer. Recent results in art galleries (geometry). Proceedings of the IEEE, 80(9):1384–1399, 1992. doi:10.1109/5.163407.
[67] Jack Stade. The point-boundary art gallery problem is $\exists\mathbb{R}$ -hard. Symposium on Computational Geometry, 2025.
[68] Rolf Svenning. RolfSvenning/ContiguousArtGallery. Software, swhId: swh:1:dir:7cfaba2c09d953feb90a49f0e26370ea3f7719a7 (visited on 2025-04-24). URL: https://github.com/RolfSvenning/ContiguousArtGallery, doi:10.4230/artifacts.23018.
[69] Xuehou Tan. Approximation algorithms for cutting out polygons with lines and rays. In Computing and Combinatorics, 11th Annual International Conference, COCOON 2005, Kunming, China, August 16-29, 2005, Proceedings, volume 3595 of Lecture Notes in Computer Science, pages 534–543. Springer, 2005. doi:10.1007/11533719_54.
[70] 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.
[71] Csaba D Tóth. 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.
[72] Csaba D Tóth. Art galleries with guards of uniform range of vision. Computational Geometry, 21(3):185–192, 2002. doi:10.1016/S0925-7721(01)00024-4.
[73] Csaba D. Tóth. Illumination of polygons by 45°-floodlights. Discret. Math., 265(1-3):251–260, 2003. doi:10.1016/S0012-365X(02)00583-6.
[74] Jorge Urrutia. Art gallery and illumination problems. In Handbook of computational geometry, pages 973–1027. Elsevier, 2000. doi:10.1016/B978-044482537-7/50023-1.
[75] 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.
[76] Chris Worman and J 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.

[bib.bib1] [1] Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow. Irrational guards are sometimes needed. In Proceedings of the 33rd International Symposium on Computational Geometry (SoCG), pages 3:1–3:15, 2017. doi:10.4230/LIPICS.SOCG.2017.3.

[bib.bib2] [2] Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow. The art gallery problem is $\exists\mathbb{R}$ -complete. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 65–73. ACM, 2018. doi:10.1145/3188745.3188868.

[bib.bib3] [3] Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow. The art gallery problem is $\exists\mathbb{R}$ -complete. J. ACM, 69(1):4:1–4:70, 2022. doi:10.1145/3486220.

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

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

[bib.bib6] [6] Alok Aggarwal, Heather Booth, Joseph O’Rourke, Subhash Suri, and Chee-Keng Yap. Finding minimal convex nested polygons. In Joseph O’Rourke, editor, Proceedings of the First Annual Symposium on Computational Geometry, Baltimore, Maryland, USA, June 5-7, 1985, pages 296–304. ACM, 1985. doi:10.1145/323233.323271.

[bib.bib7] [7] Alok Aggarwal, Heather Booth, Joseph O’Rourke, Subhash Suri, and Chee-Keng Yap. Finding minimal convex nested polygons. Inf. Comput., 83(1):98–110, 1989. doi:10.1016/0890-5401(89)90049-7.

[bib.bib8] [8] 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.

[bib.bib9] [9] Yoav Amit, Joseph S. B. Mitchell, and Eli Packer. Locating guards for visibility coverage of polygons. In Proc. Ninth Workshop on Algorithm Engineering and Experiments, Proceedings in Applied Mathematics, pages 120–134. SIAM, 2007. doi:10.1137/1.9781611972870.12.

[bib.bib10] [10] Yoav Amit, Joseph S. B. Mitchell, and Eli Packer. Locating guards for visibility coverage of polygons. International Journal of Computational Geometry & Applications, 20(5):601–630, October 2010. doi:10.1142/S0218195910003451.

[bib.bib11] [11] Stav Ashur, Omrit Filtser, Matthew J. Katz, and Rachel Saban. Terrain-like graphs: Ptass for guarding weakly-visible polygons and terrains. In Evripidis Bampis and Nicole Megow, editors, Approximation and Online Algorithms - 17th International Workshop, WAOA 2019, Munich, Germany, September 12-13, 2019, Revised Selected Papers, volume 11926 of Lecture Notes in Computer Science, pages 1–17. Springer, 2019. doi:10.1007/978-3-030-39479-0_1.

[bib.bib12] [12] 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.

[bib.bib13] [13] 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. doi:10.1007/978-3-540-69733-6_59.

[bib.bib14] [14] 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.

[bib.bib15] [15] 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.

[bib.bib16] [16] 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.

[bib.bib17] [17] Ahmad Biniaz, Anil Maheshwari, Joseph S. B. Mitchell, Saeed Odak, Valentin Polishchuk, and Thomas C. Shermer. Contiguous boundary guarding, 2024. doi:10.48550/arXiv.2412.15053.

[bib.bib18] [18] Édouard 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.

[bib.bib19] [19] 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. URL: http://www.cccg.ca/proceedings/1995/cccg1995_0022.pdf.

[bib.bib20] [20] Vasek Chvátal. A combinatorial theorem in plane geometry. Journal of Combinatorial Theory, Series B, 18(1):39–41, 1975.

[bib.bib21] [21] 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.

[bib.bib22] [22] Ovidiu Daescu and Jun Luo. Cutting out polygons with lines and rays. In Rudolf Fleischer and Gerhard Trippen, editors, Algorithms and Computation, 15th International Symposium, ISAAC 2004, Hong Kong, China, December 20-22, 2004, Proceedings, volume 3341 of Lecture Notes in Computer Science, pages 669–680. Springer, 2004. doi:10.1007/978-3-540-30551-4_58.

[bib.bib23] [23] Ovidiu Daescu and Jun Luo. Cutting out polygons with lines and rays. Int. J. Comput. Geom. Appl., 16(2-3):227–248, 2006. doi:10.1142/S0218195906002014.

[bib.bib24] [24] 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.

[bib.bib25] [25] Erik D. Demaine, Martin L. Demaine, and Craig S. Kaplan. Polygons cuttable by a circular saw. In Proceedings of the 12th Canadian Conference on Computational Geometry, Fredericton, New Brunswick, Canada, August 16-19, 2000, 2000. URL: http://www.cccg.ca/proceedings/2000/36.ps.gz.

[bib.bib26] [26] Erik D. Demaine, Martin L. Demaine, and Craig S. Kaplan. Polygons cuttable by a circular saw. Comput. Geom., 20(1-2):69–84, 2001. doi:10.1016/S0925-7721(01)00036-0.

[bib.bib27] [27] 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. doi:10.1007/978-3-540-73951-7_15.

[bib.bib28] [28] Adrian Dumitrescu and Masud Hasan. Cutting out polygons with a circular saw. In Takao Asano, Shin-Ichi Nakano, Yoshio Okamoto, and Osamu Watanabe, editors, Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Yokohama, Japan, December 5-8, 2011. Proceedings, volume 7074 of Lecture Notes in Computer Science, pages 230–239. Springer, 2011. doi:10.1007/978-3-642-25591-5_25.

[bib.bib29] [29] Adrian Dumitrescu and Masud Hasan. Cutting out polygons with a circular saw. Int. J. Comput. Geom. Appl., 23(2):127–140, 2013. doi:10.1142/S0218195913600030.

[bib.bib30] [30] Alon Efrat and Sariel Har-Peled. Guarding galleries and terrains. In Ricardo A. Baeza-Yates, Ugo Montanari, and Nicola Santoro, editors, Foundations of Information Technology in the Era of Networking and Mobile Computing, IFIP 17 ${}^{\mbox{th}}$ World Computer Congress - TC1 Stream / 2 ${}^{\mbox{nd}}$ IFIP International Conference on Theoretical Computer Science (TCS 2002), August 25-30, 2002, Montréal, Québec, Canada, volume 223 of IFIP Conference Proceedings, pages 181–192. Kluwer, 2002. doi:10.1007/978-0-387-35608-2_16.

[bib.bib31] [31] 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.

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

[bib.bib33] [33] 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. doi:10.1016/0196-6774(81)90019-5.

[bib.bib34] [34] Andreas Fabri, Geert-Jan Giezeman, Lutz Kettner, Stefan Schirra, and Sven Schönherr. On the design of cgal a computational geometry algorithms library. Software: Practice and Experience, 30(11):1167–1202, 2000. doi:10.1002/1097-024X(200009)30:11\%3C1167::AID-SPE337\%3E3.0.CO;2-B.

[bib.bib35] [35] Steve Fisk. A short proof of chvátal’s watchman theorem. Journal of Combinatorial Theory, Series B, 24(3):374, 1978. doi:10.1016/0095-8956(78)90059-X.

[bib.bib36] [36] 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.

[bib.bib37] [37] 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.

[bib.bib38] [38] 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.

[bib.bib39] [39] 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.

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

[bib.bib41] [41] 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.

[bib.bib42] [42] 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.

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

[bib.bib44] [44] James King and Erik Krohn. Terrain guarding is np-hard. In Moses Charikar, editor, Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 1580–1593. SIAM, 2010. doi:10.1137/1.9781611973075.128.

[bib.bib45] [45] James King and Erik Krohn. Terrain guarding is NP-hard. SIAM J. Comput., 40(5):1316–1339, 2011. doi:10.1137/100791506.

[bib.bib46] [46] 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.

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

[bib.bib48] [48] 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.

[bib.bib49] [49] 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.

[bib.bib50] [50] 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.

[bib.bib51] [51] 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. doi:10.1016/j.cageo.2008.08.009.

[bib.bib52] [52] Lucas Meijer and Tillmann Miltzow. Sometimes two irrational guards are needed. ArXiv, abs/2212.01211, 2022. doi:10.48550/arXiv.2212.01211.

[bib.bib53] [53] 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. doi:10.48550/arXiv.2412.13938.

[bib.bib54] [54] Joseph S. B. Mitchell and Subhash Suri. Separation and approximation of polyhedral objects. In Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’92, pages 296–306, USA, 1992. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=139404.139467.

[bib.bib55] [55] Rajeev Motwani, Arvind Raghunathan, and Huzur Saran. Covering orthogonal polygons with star polygons: The perfect graph approach. In Herbert Edelsbrunner, editor, Proceedings of the Fourth Annual Symposium on Computational Geometry, Urbana-Champaign, IL, USA, June 6-8, 1988, pages 211–223. ACM, 1988. doi:10.1145/73393.73415.

[bib.bib56] [56] 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. doi:10.1016/0022-0000(90)90017-F.

[bib.bib57] [57] Joseph O’Rourke. Galleries need fewer mobile guards: A variation on Chvátal’s theorem. Geometriae Dedicata, 14:273–283, 1983.

[bib.bib58] [58] Joseph O’Rourke. Art Gallery Theorems and Algorithms. Oxford University Press, 1987.

[bib.bib59] [59] 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. URL: http://www.cccg.ca/proceedings/1995/cccg1995_0025.pdf.

[bib.bib60] [60] 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.

[bib.bib61] [61] Mark H. Overmars and Emo Welzl. The complexity of cutting paper (extended abstract). In Proceedings of the First Annual Symposium on Computational Geometry, Baltimore, Maryland, USA, June 5-7, 1985, pages 316–321. ACM, 1985. doi:10.1145/323233.323274.

[bib.bib62] [62] 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. doi:10.48550/arXiv.2412.15567.

[bib.bib63] [63] Eliot W. Robson, Jack Spalding-Jamieson, and Da Wei Zheng. Carving polytopes with saws in 3d. In Rahnuma Islam Nisha, editor, Proceedings of the 36th Canadian Conference on Computational Geometry, CCCG 2024, Brock University, St. Catharines, Ontario, Canada, July 17 - August 19, 2024, pages 145–152, 2024.

[bib.bib64] [64] Jörg-Rüdiger Sack and Godfried T. Toussaint. Guard placement in rectilinear polygons. In Machine Intelligence and Pattern Recognition, volume 6, pages 153–175. Elsevier, 1988.

[bib.bib65] [65] 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.

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

[bib.bib67] [67] Jack Stade. The point-boundary art gallery problem is $\exists\mathbb{R}$ -hard. Symposium on Computational Geometry, 2025.

[bib.bib68] [68] Rolf Svenning. RolfSvenning/ContiguousArtGallery. Software, swhId: swh:1:dir:7cfaba2c09d953feb90a49f0e26370ea3f7719a7 (visited on 2025-04-24). URL: https://github.com/RolfSvenning/ContiguousArtGallery, doi:10.4230/artifacts.23018.

[bib.bib69] [69] Xuehou Tan. Approximation algorithms for cutting out polygons with lines and rays. In Computing and Combinatorics, 11th Annual International Conference, COCOON 2005, Kunming, China, August 16-29, 2005, Proceedings, volume 3595 of Lecture Notes in Computer Science, pages 534–543. Springer, 2005. doi:10.1007/11533719_54.

[bib.bib70] [70] 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.

[bib.bib71] [71] Csaba D Tóth. 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.

[bib.bib72] [72] Csaba D Tóth. Art galleries with guards of uniform range of vision. Computational Geometry, 21(3):185–192, 2002. doi:10.1016/S0925-7721(01)00024-4.

[bib.bib73] [73] Csaba D. Tóth. Illumination of polygons by 45°-floodlights. Discret. Math., 265(1-3):251–260, 2003. doi:10.1016/S0012-365X(02)00583-6.

[bib.bib74] [74] Jorge Urrutia. Art gallery and illumination problems. In Handbook of computational geometry, pages 973–1027. Elsevier, 2000. doi:10.1016/B978-044482537-7/50023-1.

[bib.bib75] [75] 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.

[bib.bib76] [76] Chris Worman and J 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.

Polynomial-Time Algorithms for Contiguous Art Gallery and Related Problems

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Supplementary Material:

Acknowledgements:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

1.1 Related work and results

Hardness and approximations.

Polynomial-time exact algorithms.

Combinatorial bounds.

Contiguity.

Circle-cover minimization.

Minimum Polygon Separation.

Polytope Carving.

1.2 Preliminaries

Observation 1.

1.3 Combinatorial Bounds

Lemma 2.

Theorem 3.

Proof.

1.4 Greedy Steps

Lemma 4.

Proof Sketch.

Theorem 5.

Theorem 6.

1.5 Organization

2 Finding an Optimal Solution via Repeated GreedyRevolution

2.1 Combinatorial optimality conditions

Lemma 7 (Properties of G and guardable intervals).

Proposition 8 (Behavior of non-optimal greedy sequences).

Definition 9 (Local Greedy Sequence).

2.2 Achieving optimality conditions using Geometry

Definition 10 (Fingerprint).

Definition 11 (Edge jumps).

Lemma 12 (Progress conditions).

Theorem 13 (GreedyRevolution will reach a progress condition).

Lemma 14 (The feasible region is contained in the shadow).

Proposition 15 (Feasible region over repeated pivot line implies a progress condition).

Proposition 16 (Guard placed below pivot implies other guard placed strictly above pivot).

2.3 Proof of Theorem 6

Proof of Theorem 6.

3 Simplifying the Domain of GreedyInterval

Lemma 17.

Algorithm (in a nutshell).

Lemma 18.

Theorem 19.

Remark.

4 The Analytic Arc Cover Problem

Definition 20.

Theorem 21.

4.1 Outline of approach

Analytic Arc Cover

Observation 22.

Theorem 23.

Proof.

Contiguous Art Gallery

Polygon Separation and Polytope Carving

5 Future work

References

Lemma 7 (Properties of $\operatorname{\textsc{G}}$ and guardable intervals).