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

Stade, Jack

doi:10.4230/LIPIcs.SoCG.2025.74

The Point-Boundary Art Gallery Problem Is $\exists\mathbb{R}$ -Hard

Jack Stade

University of Copenhagen, Denmark

Abstract

We resolve the complexity of the point-boundary variant of the art gallery problem, showing that it is $\exists\mathbb{R}$ -complete, meaning that it is equivalent under polynomial time reductions to deciding whether a system of polynomial equations has a real solution.

The art gallery problem asks whether there is a configuration of guards that together can see every point inside of an art gallery modeled by a simple polygon. The original version of this problem (which we call the point-point variant) was shown to be $\exists\mathbb{R}$ -hard [Abrahamsen, Adamaszek, and Miltzow, JACM 2021], but the complexity of the variant where guards only need to guard the walls of the art gallery was left as an open problem. We show that this variant is also $\exists\mathbb{R}$ -hard.

Our techniques can also be used to greatly simplify the proof of $\exists\mathbb{R}$ -hardness of the point-point art gallery problem. The gadgets in previous work could only be constructed by using a computer to find complicated rational coordinates with specific algebraic properties. All of our gadgets can be constructed by hand and can be verified with simple geometric arguments.

Keywords and phrases:

Art Gallery Problem, Complexity, ETR, Polygon

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Computational geometry

Related Version:

Full Version: https://arxiv.org/abs/2210.12817

Funding:

Supported by Independent Research Fund Denmark, grant 1054-00032B, and by the Carlsberg Foundation, grant CF24-1929.

DOI:

10.4230/LIPIcs.SoCG.2025.74

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

1.1 Art gallery problem

The original form of the art gallery problem (AGP) presented by Victor Klee (see O’Rourke [11]) asks whether a simple polygonal region $P$ can be guarded by $n$ guards. That is, whether there is a set of $n$ points (called the guards) in $P$ such that every point in $P$ is visible to some guard, meaning that the the line segment between that point and that guard is contained in $P$ . The polygon $P$ is referred to as the art gallery.

The vertices of $P$ are usually restricted to rational or integer coordinates, but even so an optimal configuration might require guards with irrational coordinates. Abrahamsen, Adamaszek and Miltzow give explicit examples that require irrational coordinates in [1]. For this reason, we don’t expect algorithms to actually output the guarding configurations, only to determine how many guards are necessary.

It is non-trivial to see that the problem is even decidable. The first exact algorithm for the most general variants of the AGP is attributed to Sharir (see Efrat and Har-Peled [7]).

1.2 The complexity class $\exists\mathbb{R}$

The decision problem ETR (Existential Theory of the Reals) asks whether a sentence of form:

\exists X_{1}\dots\exists X_{n}\Phi(X_{1},\dots,X_{n})

is true, where the $X_{i}$ are real variables and $\Phi$ is a formula in the $X_{i}$ involving $0$ , $1$ , $+$ , $-$ , $\cdot$ , $=$ , $<$ , $\leq$ , $\neg$ , $\wedge$ , and $\vee$ . The complexity class $\exists\mathbb{R}$ consists of problems that can be reduced to ETR in polynomial time. A number of interesting problems have been shown to be complete for $\exists\mathbb{R}$ , including for example packing polygons in a square [3] and the problem of deciding whether there exists a point configuration with a given order type [10, 14].

By a result of Schaefer and Stefankovic [12], the exact inequalities used don’t matter; for example we obtain an equivalent definition of $\exists\mathbb{R}$ if we don’t allow $=$ , $\leq$ , or $\neg$ in $\Phi$ . The same authors have more recently shown that similar results hold at every level of a real hierarchy, of which $\exists\mathbb{R}$ is the first level [13].

It is straightforward to show that $\text{NP}\subseteq\exists\mathbb{R}$ . It is also known, though considerably more difficult to prove, that $\exists\mathbb{R}\subseteq\text{PSPACE}$ (Canny [6]). It is unknown whether either inclusion is strict.

1.3 Art gallery variants

A natural class of variants of the art-gallery problem is given by restricting both the positions that can be occupied by the guards and the points that need to be guarded. We will adopt the notation used in [4]:

Definition 1.

(Agrawal, Knudsen, Lokshtanov, Saurabh, and Zehavi [4]) The X-Y Art Gallery problem, where $X,Y\in\{\text{Vertex},\text{Point},\text{Boundary}\}$ , asks whether the polygon $P$ can be guarded with $n$ guards, where if $X=\text{Vertex}$ the guards are restricted to lie on the vertices of the polygons, if $X=\text{Boundary}$ the guards are restricted to lie on the boundary of the polygon, and if $X=\text{Point}$ then the guards can be anywhere inside the polygon. The region that must be guarded is determined by $Y$ analogously.

Table 1 lists these variants and the known bounds on complexity.

Table 1: Variants of the art gallery problem.

If $X$ or $Y$ is Vertex, then the problem is easily seen to be in NP. Lee and Lin [9] showed that all of these variants are NP-hard (the result is stated for all the X-Point variants, but their constructions also work for the other variants. See also [8]). More recently, Abrahamsen, Adamaszek, and Miltzow [2] showed that the point-point and boundary-point variants are $\exists\mathbb{R}$ complete. It is straightforward to extend their proof of membership in $\exists\mathbb{R}$ to any of these variants, but they list $\exists\mathbb{R}$ hardness of the point-boundary variant an open problem.

1.4 Our results

Our main result is that the point-boundary variant of the art gallery problem is, up to polynomial time reductions, as hard as deciding whether a system of polynomial equations has a real solution.

Theorem 2.

The point-boundary variant of the art gallery problem is $\exists\mathbb{R}$ -complete.

While the complexity of the boundary-boundary variant is still unsolved, this is is enough to show that the the X-Y art gallery problem is equivalent to the Y-X art gallery problem for $X,Y\in\{\text{Vertex},\text{Point},\text{Boundary}\}$ .

Our ideas can also be used to considerably simplify the construction in [2]. Both the construction and verification of each of our gadgets is simpler than that of the corresponding gadget in [2]. Indeed, our gadgets can be drawn by hand with little more than compass-and-straightedge-style constructions. Each gadget is specified by a simple set of geometric properties rather than by exact coordinates. Our gadgets are quite flexible and the geometry could probably be adapted to other settings.

Our reduction is from a problem called ETR-INV-REV, which is a slight modification of a problem ETR-INV from [2]. In Section 2, we define this problem and show that it is $\exists\mathbb{R}$ -hard.

Given an instance $\Phi$ of ETR-INV-REV, we show how to construct a polygon whose boundary can be guarded by some number $n$ guards if and only if $\Phi$ has a satisfying assignment. In Section 3, we describe the overall structure of the polygon that we construct and explain how to constrain the positions of guards. In Section 4, we describe copy gadgets that are required in order to use a single variable in multiple constraints. Finally, in Section 5 we describe the gadgets that create constraints and prove Theorem 2.

Throughout, statements marked with $(\star)$ have proofs omitted. The proofs can be found in the full version.

2 ETR-INV-REV

The proof of Theorem 2 is by reduction of the problem we call ETR-INV-REV to the point-boundary variant of the art gallery problem.

Definition 3.

(ETR-INV-REV) In the problem ETR-INV-REV, we are given a set of real variables $\{x_{1},\dots,x_{n}\}$ and a set of inequalities of the form:

x=1,\quad xy\geq 1,\quad x\left(\frac{5}{2}-y\right)\leq 1,\quad x+y\leq z,% \quad x+y\geq z,

for $x,y,z\in\{x_{1},\dots,x_{n}\}$ . The problem asks whether there is an assignment of the $x_{i}$ satisfying these inequalities with each $x_{i}\in[\frac{1}{2},2]$ .

Abrahamsen, Adamaszek and Miltzow [2] proved the $\exists\mathbb{R}$ -hardness of the point-point and boundary-point variants using a similar problem called ETR-INV.

Definition 4.

(Abrahamsen, Adamaszek and Miltzow [2]) (ETR-INV) In the problem ETR-INV, we are given a set of real variables $\{x_{1},\dots,x_{n}\}$ and a set of equations of the form:

x=1,\quad xy=1,\quad x+y=z,

for $x,y,z\in\{x_{1},\dots,x_{n}\}$ . The problem asks whether there is a solution to the system of equations with each $x_{i}\in[\frac{1}{2},2]$ .

Theorem 5.

(Abrahamsen, Adamaszek, Miltzow [2]) The problem ETR-INV is $\exists\mathbb{R}$ -complete.

Regardless of the specific art gallery variant, it seems to be difficult to make a construction that admits both $xy\leq 1$ and $xy\geq 1$ constraints. The $xy\leq 1$ inversion gadget in [2] is actually closer to a $x\left(\frac{5}{2}-y\right)\leq 1$ gadget, and another gadget is used to compute a constraint like $y^{\prime}=\left(\frac{5}{2}-y\right)$ . By reducing from ETR-INV-REV instead, our construction avoids the need for a reversing gadget.

Theorem 6.

$(\star)$ The problem ETR-INV-REV is $\exists\mathbb{R}$ -hard.

3 Arranging the art gallery

Throughout this section, and the rest of the paper, $A B$ refers to a line segment with endpoints $A$ and $B$ , $\overleftrightarrow{AB}$ is the line containing that segment, and $|AB|$ is the length of that segment.

3.1 Creating guard regions

We will designate some number $n$ of disjoint guard regions inside the art gallery such that any guarding configuration with $n$ guards must have exactly one guard in each region. Each guard region is determined by wedges on the polygon boundary. Each wedge is formed by two edges of the art gallery meeting at a convex corner. The visibility region of a wedge is the set of points that can see the tip of the wedge. A wedge and its visibility region is shown in Figure 1 (left).

Figure 1: Left: A wedge (

W

) and its visibility region (

V

). Right: The intersection of the visibility regions of the three wedges shown forms a guard segment. This method of using

3

wedges to form a guard segment is due to Bertschinger, El Maalouly, Miltzow, Schnider and Weber [5] and is a slight simplification of the method for forming guard segments from [2].

In a guarding configuration, the visibility region of each wedge must contain a guard. We designate a guard region by specifying some (non-zero) number of wedges, and the guard region is the intersection of the visibility regions of those wedges. These must be chosen that visibility regions of any two wedges corresponding to different guard regions do not intersect. A guard region shaped like a line segment is called a guard segment, as in Figure 1 (right).

Lemma 7.

If we designate $n$ guard regions, then any guarding configuration has at least $n$ guards, and a guarding configuration with exactly $n$ guards has $1$ guard in each guard region.

Proof.

Choose wedges $w_{1},\dots,w_{n}$ , one from each of the guard regions. The guard regions are chosen so that the visibility regions of these wedges do not intersect. In a guarding configuration, each of these regions contains at least $1$ guard. Since these region do not intersect, this requires at least $n$ guards.

If a guarding configuration contains exactly $n$ guards, then there will be exactly $1$ guard in the visibility region of $w_{i}$ for each $i$ . Consider the guard region containing $w_{j}$ and suppose $v$ is another wedge forming that guard region. There is a guard in the visibility region of $v$ , and this region doesn’t intersect the visibility region of $w_{i}$ for $i\neq j$ , so this guard must be the one in $w_{j}$ . Repeating this argument for the other wedges forming this guard region, we see that the guard in $w_{j}$ must be in each of them. So the guard is in the guard region.

So a guarding configuration with exactly $n$ guards has $1$ guard in each guard region. $\hfill\blacktriangleleft$

The guard segments in our construction will all be vertical, and the position of a guard on a guard segment will encode a variable in the interval $[\frac{1}{2},2]$ , with the bottom endpoint of the interval corresponding to $\frac{1}{2}$ and the top endpoint corresponding to $2$ .

3.2 Constraint nooks

We use constraint nooks to enforce constraints involving multiple variables. Each nook consists of a line segment on the boundary of the art gallery, called the nook segment, and two polygon vertices called opening points. The region of partial visibility of a nook is the set of points which can see some part of the nook segment.

If the nook segment has endpoints $A$ and $B$ and the opening points are $E$ and $F$ where $E, A, B, F$ occur in that order on the polygon boundary, then we say that $E$ restricts $A$ and $F$ restricts $B$ (see Figure 2).

These are slightly more general than the nooks from [2], in that it will sometimes be necessary to intersect a wedge with a nook, as in Figure 2 (left).

Figure 2: Left: A nook with nook segment

A B

, opening points

E

restricting

A

and

F

restricting

B

, and partial visibility region

V

. The outer parts of

V

(lighter) can only see part of the nook segment. Right: This art gallery can be guarded by two guards, but there is no such configuration where the nook segment on the left is guarded entirely by a single guard. This creates a continuous constraint between the positions of the two guards.

A guarding configuration will have some non-zero number of guards in the partial visibility region of a nook, that together must guard the nook segment, as in Figure 2 (right). Multiple guards can collaborate to guard a single nook segment, creating a continuous dependence between the positions of those guards.

3.3 Schematic of the art gallery

Figure 3: A schematic of the art gallery that we construct (not to scale). The variables are encoded by positions of guards on the variable segments (red, middle). The constraint gadgets on the bottom right enforce constraints like

xy\geq 1

or

x+y\leq z

on the variables encoded by the input segments (red, bottom right). The copy nooks copy the values of the appropriate variables onto the input segments. The wedges creating the segment-shaped guard regions can be seen along the top and bottom walls of the art gallery.

Figure 3 shows a schematic of the entire art gallery construction. We start with an instance $\Phi$ of ETR-INV-REV with variables $x_{1},\dots,x_{n}$ and constraints of form:

x=1,\quad xy\geq 1,\quad x\left(\frac{5}{2}-y\right)\leq 1,\quad x+y\leq z,% \quad x+y\geq z,

Each variable is represented by a guard region called a variable segment. The variable segments are arranged in a row near the middle of the art gallery. The height of a guard on a variable segment corresponds linearly to the value of the variable encoded, with the bottom of the variable segment mapping to $\frac{1}{2}$ and the top mapping to $2$ .

Figure 4: Four wedges create a point-shaped guard region.

The constraints of form $x=1$ in $\Phi$ are created by adding wedges to create a guard region consisting of only a single point, as shown in Figure 4. Each constraint involving more than one variable is created by a constraint gadget, which we place in a row on the bottom right of the art gallery. The constraint gadgets are modular in the sense that they (almost) do not depend on $\Phi$ . Each constraint gadget operates on either $2$ or $3$ guard segments called input segments. Nooks in the constraint gadget create constraints on the variables represented by the guards on the input segments.

Each input segment can only appear in one constraint gadget, so we need copy nooks to relate each input segment to the variable segment for the variable that it represents.

4 Construction of the copy nooks

If a guard on a variable segment encodes a value $x$ and a guard on an input segment encodes a value $y$ , then a copy nook creates a constraint like $x\leq y$ or $x\geq y$ . Figure 5 shows an example of a copy nook enforcing a constraint like $x\geq y$ . This type of copy nook is due to Stade and Tucker-Foltz [15].

4.1 Verifying a single copy nook

Figure 5: A copy nook, shown in the situation where the guard positions don’t fully guard the nook.

Lemma 8.

Suppose segments $A B$ and $C D$ are such that $\overleftrightarrow{AB}$ and $\overleftrightarrow{CD}$ are parallel, and suppose $\overleftrightarrow{AC}$ and $\overleftrightarrow{BD}$ intersect at a point $P$ , as in Figure 6. If a line through $P$ intersects $A B$ at a point $X$ and intersects $C D$ at a point $Y$ , then $\frac{|AX|}{|AB|}=\frac{|CY|}{|CD|}$ .

Proof.

Triangles $A P B$ and $C P D$ are similar, so $\frac{|AP|}{|AB|}=\frac{|CP|}{|CD|}$ . Also, the triangles $A X P$ and $C Y P$ are similar, so $\frac{|AX|}{|AP|}=\frac{|CY|}{|CP|}$ . Multiplying, we obtain $\frac{|AX|}{|AB|}=\frac{|CY|}{|CD|}$ . $\hfill\blacktriangleleft$

Figure 6: Setup for Lemma 8.

Lemma 9.

Suppose that $A B$ and $C D$ are parallel guard segments and there is a nook with nook segment $E F$ that is parallel to $A B$ and $C D$ . Suppose the nook has openings points $P$ on the intersection point of $\overleftrightarrow{AE}$ and $\overleftrightarrow{BF}$ and $Q$ on the intersection of $\overleftrightarrow{BE}$ and $\overleftrightarrow{CF}$ so that $P$ restricts $F$ and $Q$ restricts $G$ .

Suppose also that the nook is unobstructed, that is that every segment through $P$ from a point on $A B$ to a point on $E F$ is contained in the art gallery and segments through $Q$ are similarly unobstructed.

Then guards at positions $X$ and $Y$ on $A B$ and $C D$ respectively guard the nook if and only if:

\frac{|AX|}{|AB|}\geq\frac{|CY|}{|CD|}

The setup for Lemma 9 is shown in Figure 5. The proof is a straightforward application of Lemma 8.

Figure 7: A guard (

g_{1}

) on a variable segment and a guard (

g_{2}

) on an input segment are related by two copy nooks. The upper nook is guarded when the value encoded by

g_{1}

is at least the value encoded by

g_{2}

, and the lower nook is guarded when the value encoded by

g_{1}

is at most the value encoded by

g_{2}

.

By changing which intersection point restricts which endpoint of the nook segment, we can create a constraint either $x\leq y$ or $x\geq y$ . Figure 7 shows a pair of guard segments with both types of copy nook between them.

Enforcing a constraint $x=y$ requires $2$ nooks, but all of the constraints allowed by ETR-INV-REV are monotone with respect to any single variable, so we only need a single copy nook for each input segment. For example, $xy\geq 1$ is equivalent to $x^{\prime}y^{\prime}\geq 1$ , $x\geq x^{\prime}$ and $y\geq y^{\prime}$ (when there are no other constraints on $x^{\prime}$ and $y^{\prime}$ ).

In the full version, we show that it is possible to arrange all the copy nooks in such a way that none of them interfere with each other. This construction ensures that the partial visibility region of each copy nook is bounded by lines with slope between $-\frac{1}{2}$ and $-1$ , a fact that will be useful in order to make sure that the constraint gadgets don’t interfere with the copy nooks.

5 The constraint gadgets

We start with some specifications that a constraint gadget should adhere to in order to be compatible with the copy nooks. There are several bad cases that we need to prevent:

$\blacksquare$

The constraint gadget obstructs the visibility between an input segment and a copy nook.
$\blacksquare$

A guard on a variable segment can see part of a nook segment in the constraint gadget.
$\blacksquare$

An guard used by the gadget (called an auxiliary guard) can see part of the nook segment of a copy nook.

For each constraint gadget, we designate $R_{1}$ and $R_{2}$ , shown in Figure 8. The region $R_{1}$ is bounded by the convex hull of the input segments to that gadget and lines of slope $-\frac{1}{2}$ and $-1$ through the bottom of the leftmost input segment and the top of the rightmost input segment respectively. $R_{2}$ is the set of points that can be connected to a point outside of the constraint gadget by a line segment that is contained in the polygon and has slope between $-1$ and $0$ .

Figure 8: Diagram of a constraint gadget. The region

R_{1}

is bounded by lines with slope

-1

and

-\frac{1}{2}

. The region

R_{2}

is bounded by lines with slope

-1

and the polygon wall. The yellow region is a an auxiliary guard region, which must not intersect

R_{2}

.

Lemma 10.

The region $R_{1}$ contains all possible sight lines between an input segment and the nook segment of one of the copy nooks, so if the constraint gadget does not have any walls that intersect this region then it will not obstruct the copy gadgets.

Proof.

The construction in Section 4 ensures that all sight lines between an input segment and a nook segment have slope between $-1$ and $-\frac{1}{2}$ , and so are contained in the region $R_{1}$ . $\hfill\blacktriangleleft$

Lemma 11.

The only points in a constraint gadget that can be seen by a variable segment are in $R_{2}$ . So any nook with a nook segment that doesn’t intersect $R_{2}$ must be guarded by guards on input segments or auxiliary guards in that gadget.

Points in a constraint gadget outside of $R_{2}$ cannot see any part of the nook segment of any copy nook. So if any auxiliary guard regions don’t overlap $R_{2}$ , then a guard in that region can’t help guard any of the copy nooks.

Proof.

The construction of the copy nooks ensures that any line between a variable segment and a point at the top of a constraint gadget has slope between $-1$ and $0$ . Any sight line between a point on a variable segment and a point in the constraint gadget must pass through the top, so any such line has slope between $-1$ and $0$ . So $R_{2}$ contains all points in the constraint gadget that can be seen by a point on a variable segment.

The construction of the copy nooks also ensures that the partial visibility region of each copy nook is bounded by lines with slope between $-1$ and $-\frac{1}{2}$ . So the only points in a constraint gadget that can see part of a nook segment of a copy nook are in $R_{2}$ . $\hfill\blacktriangleleft$

5.1 Inversion gadgets

Each inversion gadget consists of a single constraint nook interacting with the two input variables. Figures 9 and 10 show the $xy\geq 1$ and $x\left(\frac{5}{2}-y\right)\leq 1$ inversion gadgets respectively. Figures 11 and 12 show the geometry of these gadgets in more detail.

Figure 9: The

xy\geq 1

inversion gadget. The two red segments are the input segments, with the left segment representing the variable

x

and the right segment representing

y

. Both guards see more of the nook segment the higher they are. The blue segment is a “phantom” segment that is used to help verify the gadget.

Figure 10: The

x\left(\frac{5}{2}-y\right)\leq 1

inversion gadget. Compared to the

xy\geq 1

gadget, the guard on the left segment (representing

x

) now sees more of the nook segment when it is lower.

In either gadget, we suppose that there is a guard at $X$ on the input segment $G H$ . The nook has opening points $P$ and $Q$ , so the guard at $X$ can see all the points to the left of point $Y$ on the nook segment $I J$ . For the $xy\geq 1$ gadget, this means that a guard on $A B$ see the rest of $I J$ if and only if it is above the point $W$ . For the $x\left(\frac{5}{2}-y\right)\leq 1$ gadget, a guard on $A B$ should be below $W$ instead.

Figure 11: Labeled diagram of the

xy\geq 1

inversion gadget shown in Figure 10.

Figure 12: Labeled diagram of the

x\left(\frac{5}{2}-y\right)\leq 1

inversion gadget shown in Figure 9.

In both cases, the guard on $A B$ represents the input $x$ and the guard on $G H$ represents the input $y$ . The segments represent the intervals $[\frac{1}{2},2]$ , with lower points on the segments corresponding to lower values. So we should show that:

\left(\frac{3}{2}\cdot\frac{|AW|}{|AB|}+\frac{1}{2}\right)\left(\frac{3}{2}% \cdot\frac{|GX|}{|GH|}+\frac{1}{2}\right)=1

for any $X$ on $G H$ and $W$ on $A B$ as shown.

Figure 13: As long as the points

P

,

Y

, and

Z

are colinear, then the value of

|EZ||FY|

does not depend on the positions of

Y

and

Z

, so the positions of

Z

and

Y

are related by inversion. The curved relationship occurs because

A B

and

C D

are not parallel.

Lemma 12.

If line segments $A B$ and $C D$ are not parallel, as in Figure 13, let $P$ be the intersection of $\overleftrightarrow{AD}$ and $\overleftrightarrow{BC}$ . Let $E$ be the point on $\overleftrightarrow{AB}$ such that $\overleftrightarrow{PE}$ and $\overleftrightarrow{CD}$ are parallel, and let $F$ be the point on $\overleftrightarrow{CD}$ such that $\overleftrightarrow{PF}$ and $\overleftrightarrow{AB}$ are parallel. Suppose that a point $Y$ on $C D$ and a point $Z$ on $A B$ are such that $P$ , $Y$ and $Z$ are collinear. Then $\frac{|EA|}{|EB|}=\frac{|FC|}{|FD|}$ , and letting $\alpha^{2}=|EA||EB|$ and $\beta^{2}=|FC||FD|$ we have $\frac{|EZ|}{\alpha}\cdot\frac{|FY|}{\beta}=1$ .

Proof.

The triangles $E P X$ and $F Y P$ are similar, so $\frac{|EZ|}{|EP|}=\frac{|FP|}{|FY|}$ , so $|EZ||FY|=|FP||EP|$ . In particular, when $Z=A$ , we have $|EA||FD|=|FP||EP|$ , and when $Z=B$ , we have $|EB||FC|=|FP||EP|$ , so $|EA||FD|=|EB||FC|$ and $\frac{|EA|}{|EB|}=\frac{|FC|}{|FD|}$ .

Now $|EZ||FY|=|FP||EP|=|EA||FD|=|EB||FC|$ , so:

|EZ||FY|=\sqrt{|EA||FD||EB||FC|}=\sqrt{\alpha^{2}\beta^{2}}=\alpha\beta\

$\hfill\blacktriangleleft$

The formulas $\frac{|EZ|}{\alpha}$ and $\frac{|EY|}{\beta}$ give mappings from points on the input segments to $\mathbb{R}$ . We want the input segment to correspond to the intervals $[\frac{1}{2},2]$ , so we choose $|EB|=4|EA|$ (and therefore $|FD|=4|FC|$ ), so $\alpha=2|EA|=\frac{1}{2}|EB|$ and $\beta=2|FC|=\frac{1}{2}|FD|$ . This means that $\frac{|EZ|}{\alpha}$ and $\frac{|FY|}{\beta}$ will map the segments $A B$ and $C D$ respectively onto $[\frac{1}{2},2]$ .

On its own, Lemma 12 could be used to construct a nook which enforces an inversion constraint on two input segments which aren’t parallel. The input segments to a constraint gadget should be parallel, so we will need the result of Lemma 13 to correct the orientation.

Figure 14: If

X

is on

G H

, then define

Y

by projecting

X

onto

I J

through

Q

and then projecting that point onto

C D

through

P

. The relative position of

X

on

G H

is the same as the relative position of

Y

on

C D

.

Lemma 13.

Suppose line segments $G H$ , $C D$ , and $I J$ are such that $\overleftrightarrow{GH}$ , $\overleftrightarrow{CD}$ , and $\overleftrightarrow{IJ}$ all intersect at a point $O$ , as in Figure 14. Also suppose that the ratios $\frac{|OG|}{|OH|}$ and $\frac{|OC|}{|OD|}$ are the same. Let $P$ be the point where $I D$ and $J C$ intersect, and $Q$ be the point where $I H$ and $J G$ intersect. Suppose that points $X$ on $G H$ , $Y$ on $C D$ and $W$ on $I J$ are such that $W$ , $P$ , and $Y$ are collinear and $W$ , $Q$ and $X$ are collinear. Then $\frac{|GX|}{|GH|}=\frac{|CY|}{|CD|}$ .

Proof.

Place the figure in the vector space $\mathbb{R}^{2}$ with the point $O$ at $(0,0)$ . We will show that there is a linear map which sends points $G, X$ and $H$ to $C, Y$ and $D$ respectively.

The pairs of vectors $\{I,G\}$ and $\{I,C\}$ are each bases for $\mathbb{R}^{2}$ . Let $\theta$ be the linear isomorphism $\mathbb{R}^{2}\rightarrow\mathbb{R}^{2}$ which sends a vector $V$ to the coefficients $(t,s)$ such $V=tI+sG$ , and let $\psi$ be a similar map which writes $V$ as $tI+sC$ . Now the linear map $\psi^{-1}\circ\theta$ fixes points on the line containing $I$ and $J$ , and sends $G$ to $C$ . Since $\frac{|OA|}{|OB|}=\frac{|OC|}{|OD|}$ , this map sends $H$ to $D$ , and so sends $Q$ to $P$ . The point $W$ is fixed, so the line $\overleftrightarrow{WQ}$ is sent to $\overleftrightarrow{WP}$ , meaning that $X$ is sent to $Y$ . So points $G, X$ and $H$ are sent to $C, Y$ and $D$ respectively. Since linear maps preserve ratios of distances along a line, we see that:

\frac{|GX|}{|GH|}=\frac{|CY|}{|CD|}\

$\hfill\blacktriangleleft$

Note that the mappings from $G H$ to $I J$ and from $I J$ to $C D$ are in general not linear, only the composition is.

Lemma 14.

In either the $xy\geq 1$ or $x\left(\frac{5}{2}-y\right)\leq 1$ gadget, suppose there are points $C$ on $\overleftrightarrow{JP}$ and $D$ on $\overleftrightarrow{IP}$ such that $\overleftrightarrow{GH}$ , $\overleftrightarrow{CD}$ and $\overleftrightarrow{IJ}$ all intersect at a point $O$ , with $C$ and $D$ satisfying:

\frac{|OG|}{|OH|}=\frac{|OC|}{|OD|}

Suppose also that there are points $E$ on $\overleftrightarrow{AB}$ and $F$ on $\overleftrightarrow{CD}$ so that $A$ is between $E$ and $B$ , $C$ is between $F$ and $D$ , $\overleftrightarrow{PF}$ and $\overleftrightarrow{AB}$ are parallel and $\overleftrightarrow{PE}$ and $\overleftrightarrow{CD}$ are parallel, with $|FD|=4|FC|$ and $|EB|=4|EA|$ . Then:

\left(\frac{3}{2}\cdot\frac{|AW|}{|AB|}+\frac{1}{2}\right)\left(\frac{3}{2}% \cdot\frac{|GX|}{|GH|}+\frac{1}{2}\right)=1

so the two inversion gadgets enforce the appropriate constraints.

Proof.

Examples of points $C$ , $D$ , $E$ and $F$ with these properties are shown in Figures 11 and 12. Let $Z$ be the intersection of $\overleftrightarrow{YP}$ with $C D$ . By Lemma 13:

\frac{|GX|}{|GH|}=\frac{|CZ|}{CD}

By Lemma 12, we have that:

\frac{|EW|}{2|EA|}\cdot\frac{|FZ|}{2|FC|}=1

Since $4|EA|=|EB|=\frac{4}{3}|AB|$ , we have that:

\left(\frac{3}{2}\cdot\frac{|AW|}{|AB|}+\frac{1}{2}\right)=\left(\frac{|AW|}{2% |EA|}+\frac{|EA|}{2|EA|}\right)=\frac{|EW|}{2|EA|}

Similarly:

\left(\frac{3}{2}\cdot\frac{|GX|}{|GH|}+\frac{1}{2}\right)=\left(\frac{3}{2}% \cdot\frac{|CZ|}{|CD|}+\frac{1}{2}\right)=\frac{|FZ|}{2|FC|}

So:

\left(\frac{3}{2}\cdot\frac{|AW|}{|AB|}+\frac{1}{2}\right)\left(\frac{3}{2}% \cdot\frac{|GX|}{|GH|}+\frac{1}{2}\right)=1\

$\hfill\blacktriangleleft$

It remains to show that gadgets satisfying the conditions of Lemma 14 can actually be created. The most direct approach would require solving a quadratic equation, potentially introducing irrational coordinates. The authors of [2] solved a similar issue with their inversion gadgets by carefully choosing coordinates that yield quadratic equations with rational solutions. However, our gadgets can be constructed more geometrically.

Lemma 15.

$(\star)$ Geometry for the $xy\geq 1$ and $x\left(\frac{5}{2}-y\right)\leq 1$ gadgets can be constructed in a way that satisfies the conditions of Lemmas 14, 10, and 11. This does not require irrational coordinates.

5.2 Addition gadgets

Each nook creates a constraint between the positions of only $2$ guards, but the addition gadgets should create a constraint involving $3$ variables. This can be accomplished by allowing both coordinates of one guard to vary, as illustrated in Figure 15.

Figure 15: Creating a constraint between

3

variables. The guard

g_{1}

,

g_{2}

and

g_{3}

each see part of one of the nook segments. If the three shaded regions intersect, then a guard

g_{4}

can be placed in the intersection so that

g_{4}

guards the parts of the nook segments that aren’t guarded by

g_{1}

,

g_{2}

and

g_{3}

. If the three shaded regions do not intersect, then this isn’t possible.

The addition gadgets are shown in Figures 16 and 17. Each gadget has $3$ input segments, an auxiliary guard region, and three constraint nooks. Each constraint nook creates a constraint between the auxiliary guard and one input segment.

Figure 16: The

x+y\leq z

addition gadget. The partial visibility regions of the

3

nooks are marked, as is the visibility region of the wedge forming the auxiliary guard region. The auxiliary guard will need to be somewhere in the purple shaded region.

Figure 17: The

x+y\geq z

addition gadget.

The gadget can be guarded when it is possible to place a guard in the auxiliary guard region so that it can see the parts of the nook segments that aren’t visible to the input guards. We can use Lemma 8 to control the relationship between the positions of the guards on the input segments and their “shadows” on the nook segments. Lemma 16 allows us to determine what parts of these nook segments can be seen by an auxiliary guard.

Lemma 16.

Suppose the line segments $A B$ , $C D$ , and $E F$ have the same length and lie on the same vertical line, as in Figure 18, and suppose $|CB|=|DE|$ . Let points $P$ , $Q$ , and $R$ lie on a vertical line, with $|QP|=|QR|$ . Note that $\overleftrightarrow{AP}$ , $\overleftrightarrow{CQ}$ , and $\overleftrightarrow{ER}$ intersect in a single point, and the same is true of $\overleftrightarrow{BP}$ , $\overleftrightarrow{DQ}$ , and $\overleftrightarrow{FR}$ .

Suppose points $X$ and $Y$ lie on $A B$ and $E F$ respectively. Now $\overleftrightarrow{XP}$ and $\overleftrightarrow{YQ}$ intersect at a point $I$ . Let $Z$ be the point on the intersection of $C D$ and $\overleftrightarrow{IQ}$ .

If all is as above, then $\frac{1}{2}\left(|AX|+|EY|\right)=|CZ|$ .

Figure 18: By Lemma 16,

\frac{1}{2}\left(|AX|+|EY|\right)=|CZ|

.

Proof.

The idea is to transform the geometry from Figure 18 to obtain something like Figure 19.

Figure 19: A projective transformation sends points

P

,

Q

, and

R

to points

P^{\prime}

,

Q^{\prime}

and

R^{\prime}

at infinity, so the family of lines through any one of these points is sent to a family of parallel lines.

This transformation should send straight lines to straight lines and should fix the line containing points $A, B, C, D, E, F, X, Y$ and $Z$ . Additionally, the points $P$ , $Q$ and $R$ should be sent to “infinity”, lines through $P$ should be sent to lines with slope $-1$ , lines through $Q$ should be sent to lines with slope $0$ , and lines through $R$ should be sent to lines with slope $+1$ . If such a transformation exists, then it is clear by straightforward linear algebra that $\frac{1}{2}\left(|AX|+|EY|\right)=|CZ|$ .

Isomorphisms of the projective space $\mathbb{R}P^{2}$ send straight lines to straight lines. A degrees-of-freedom argument would be sufficient to find a transformation of projective space with the required properties. Instead we just give it explicitly. Assume that the line containing $A$ and $B$ is vertical, and let $x_{0}$ be the $x$ -coordinate of this line. Let $x_{1}$ be the $x$ -coordinate of $P, Q$ and $R$ , $y_{0}$ the $y$ -coordinate of $Q$ , and let $a=|QP|=|QR|$ , so $P$ has $y$ -coordinate $y_{0}+a$ and $R$ has $y$ -coordinate $y_{0}-a$ . Then the transformation $(x,y)\rightarrow(x^{\prime},y^{\prime})$ with the desired properties is defined by:

\begin{bmatrix}x_{0}+a&0&-(x_{1}+a)x_{0}\\ y_{0}&x_{0}-x_{1}&-y_{0}x_{0}\\ 1&0&-x_{1}\end{bmatrix}\begin{bmatrix}x\\ y\\ 1\end{bmatrix}=\lambda\begin{bmatrix}x^{\prime}\\ y^{\prime}\\ 1\end{bmatrix}

Writing the map in this form makes it easy to check what happens to lines through $P$ , $Q$ , and $R$ . In particular, for a $3\times 3$ matrix $A$ , if:

A\begin{bmatrix}p_{x}\\ p_{y}\\ 1\end{bmatrix}=\begin{bmatrix}a\\ b\\ 0\end{bmatrix}

then the map $(x,y)\rightarrow(x^{\prime},y^{\prime})$ given by:

\lambda\begin{bmatrix}x^{\prime}\\ y^{\prime}\\ 1\end{bmatrix}=A\begin{bmatrix}x\\ y\\ 1\end{bmatrix}

sends lines through $(p_{x},p_{y})$ to lines parallel to $\begin{bmatrix}a\\ b\end{bmatrix}$ .

Note that the setup used here is very similar the addition gadgets in [2], although our verification is different. $\hfill\blacktriangleleft$

We want to create gadgets enforcing $x+y=z$ , not $\frac{1}{2}(x+y)=z$ , so we need to use Lemma 8 to change the scale and offset of $z$ . A schematic of the nooks used by the addition gadgets are shown in Figures 20 and 21.

Figure 20: Schematic of the

x+y\leq z

addition gadget. In the actual gadgets, the lines bounding all the visibility regions have positive slopes as shown in Figures 17 and 16, but it is not possible to draw this faithfully at a readable scale.

Figure 21: The nooks for the

x+y\geq 1

gadget.

Lemma 17.

$(\star)$ It is possible to construct addition gadgets enforcing constraints $x+y\geq z$ or $x+y\leq z$ .

5.3 Final verification

Lemma 18.

Given an instance $\Phi$ of ETR-INV-REV, it is possible to construct in polynomial time an art gallery $P$ and a number $n$ so that $P$ can be guarded by $n$ guards if and only if $\Phi$ is satisfiable.

Proof.

First, create corresponding constraint gadgets for every constraint of form $xy\leq 1$ , $x\left(\frac{5}{2}-y\right)\leq 1$ , $x+y\leq z$ , or $x+y\geq z$ that occurs in $\Phi$ . Arrange these in a horizontal row along the bottom of the art gallery so that all the input segments occur in a horizontal row and the distance between any pair of input segments is a multiple of $d=5$ times the length of a single input segment.

The construction in Section 4 can be used to place the copy nooks and variable segments. Now connect all the pieces of the art gallery and add the wedges forming all the guard segments. These wedges should be chosen to be sufficiently narrow so that visibility regions of wedges from different guard regions do not intersect.

It is straightforward to check that this construction can be done in polynomial time and that the coordinates needed are rational numbers with at most polynomially many bits.

There are $n$ guard regions, consisting of the variable segments, input segments, and auxiliary guards. By Lemma 7, any guarding configuration with $n$ guards must have one guard in each guard region. Conversely, any guarding configuration with one guard in each guard can clearly guard all of these wedges.

There are some walls of the art gallery that aren’t part of the wedges, copy nooks, or constraint gadgets. The top, bottom, and right walls of the art gallery can be guarded by any guard on a variable segment. For any two copy nooks, a segment connecting can always be guarded by either of the guards on the variable segments in the visibility regions of those nooks. So any guarding configuration with one guard in each guard region will guard everything expect for possibly the copy nook and constraint gadgets.

By Lemmas 14 and 17, each constraint gadget can be guarded if and only if the guards on its input segments represent variables satisfying the corresponding constraint. Whenever a variable in $\Phi$ appears in a constraint, there are copy nooks between that variable segment and an input segment to the gadget representing that constraint. By Lemma 9, these copy nooks are guarded if and only if the guard on the input segment and the guard on the variable segment represent the value in $[\frac{1}{2},2]$ .

So $P$ can be guarded by $n$ guards if and only if $\Phi$ has a satisfying assignment. $\hfill\blacktriangleleft$

The $\exists\mathbb{R}$ -hardness of the point-boundary art-gallery problem follows from the $\exists\mathbb{R}$ -hardness of ETR-INV-REV, proving Theorem 2.

6 Conclusions

Our result shows that the X-Y and Y-X variants of the art gallery problem are equivalent under polynomial time reductions when $X,Y\in\{\text{Vertex},\text{Point},\text{Boundary}\}$ . Visibility is reflexive, so this result seems unsurprising. Maybe it could be proven more directly.

It is interesting to note that our construction, while intended for the point-boundary variant of the art gallery problem, is also sufficient to show the $\exists\mathbb{R}$ -hardness of the standard point-point variant. When it is possible to guard an art gallery produced by our construction in the point-boundary setting, the same guarding configuration is also a point-point guarding configuration. Something similar happens in [2], where the construction for the boundary-point variant is also a construction for the point-point variant. It doesn’t seem to be possible to adapt either construction to the boundary-boundary variant.

Unlike the construction from [2], the nook segments in our construction can be chosen to all be axis-parallel. Each other segment is always entirely guarded by a single guard. It may be possible to adapt our construction to show that guarding orthogonal polygons is $\exists\mathbb{R}$ -hard.

References

[1] Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow. Irrational Guards are Sometimes Needed. In Boris Aronov and Matthew J. Katz, editors, 33rd International Symposium on Computational Geometry (SoCG 2017), volume 77 of Leibniz 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.
[2] Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow. The art gallery problem is $\exists\mathbb{R}$ -complete. Journal of the ACM, 69(1):1–70, 2021. doi:10.1145/3486220.
[3] Mikkel Abrahamsen, Tillmann Miltzow, and Nadja Seiferth. Framework for er-completeness of two-dimensional packing problems. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1014–1021, 2020. doi:10.1109/FOCS46700.2020.00098.
[4] Akanksha Agrawal, Kristine V. K. Knudsen, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. The Parameterized Complexity of Guarding Almost Convex Polygons. In Sergio Cabello and Danny Z. Chen, editors, 36th International Symposium on Computational Geometry (SoCG 2020), volume 164 of Leibniz International Proceedings in Informatics (LIPIcs), pages 3:1–3:16, Dagstuhl, Germany, 2020. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.SoCG.2020.3.
[5] Daniel Bertschinger, Nicolas El Maalouly, Tillmann Miltzow, Patrick Schnider, and Simon Weber. Topological art in simple galleries. In Symposium on Simplicity in Algorithms (SOSA), pages 87–116. Society for Industrial and Applied Mathematics, January 2022. doi:10.1137/1.9781611977066.8.
[6] John Canny. Some algebraic and geometric computations in pspace. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC ’88, pages 460–467, New York, NY, USA, 1988. Association for Computing Machinery. doi:10.1145/62212.62257.
[7] Alon Efrat and Sariel Har-Peled. Guarding galleries and terrains. Inf. Process. Lett., 100:238–245, January 2006. doi:10.1007/978-0-387-35608-2_16.
[8] Aldo Laurentini. Guarding the walls of an art gallery. The Visual Computer, 15:265–278, October 1999. doi:10.1007/s003710050177.
[9] D. T. Lee and Arthur K. Lin. Computational complexity of art gallery problems. IEEE Transactions on Information Theory, 32(2):276–282, 1986. doi:10.1109/TIT.1986.1057165.
[10] Nikolai E Mnëv. The universality theorems on the classification problem of configuration varieties and convex polytopes varieties. In Topology and geometry—Rohlin seminar, pages 527–543. Springer, 1988.
[11] Joseph O’Rourke. Art gallery theorems and algorithms, volume 57. Oxford New York, NY, USA, 1987.
[12] Marcus Schaefer and Daniel Stefankovic. Fixed points, nash equilibria, and the existential theory of the reals. Theory of Computing Systems, 60:172–193, 2017. doi:10.1007/S00224-015-9662-0.
[13] Marcus Schaefer and Daniel Štefankovič. Beyond the existential theory of the reals. Theor. Comp. Sys., 68(2):195–226, December 2023. doi:10.1007/s00224-023-10151-x.
[14] Peter W. Shor. Stretchability of pseudolines is np-hard. In Applied Geometry And Discrete Mathematics, 1990.
[15] Jack Stade and Jamie Tucker-Foltz. Topological Universality of the Art Gallery Problem. In Erin W. Chambers and Joachim Gudmundsson, editors, 39th International Symposium on Computational Geometry (SoCG 2023), volume 258 of Leibniz International Proceedings in Informatics (LIPIcs), pages 58:1–58:13, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.SoCG.2023.58.

[bib.bib1] [1] Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow. Irrational Guards are Sometimes Needed. In Boris Aronov and Matthew J. Katz, editors, 33rd International Symposium on Computational Geometry (SoCG 2017), volume 77 of Leibniz 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.

[bib.bib2] [2] Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow. The art gallery problem is $\exists\mathbb{R}$ -complete. Journal of the ACM, 69(1):1–70, 2021. doi:10.1145/3486220.

[bib.bib3] [3] Mikkel Abrahamsen, Tillmann Miltzow, and Nadja Seiferth. Framework for er-completeness of two-dimensional packing problems. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1014–1021, 2020. doi:10.1109/FOCS46700.2020.00098.

[bib.bib4] [4] Akanksha Agrawal, Kristine V. K. Knudsen, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. The Parameterized Complexity of Guarding Almost Convex Polygons. In Sergio Cabello and Danny Z. Chen, editors, 36th International Symposium on Computational Geometry (SoCG 2020), volume 164 of Leibniz International Proceedings in Informatics (LIPIcs), pages 3:1–3:16, Dagstuhl, Germany, 2020. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.SoCG.2020.3.

[bib.bib5] [5] Daniel Bertschinger, Nicolas El Maalouly, Tillmann Miltzow, Patrick Schnider, and Simon Weber. Topological art in simple galleries. In Symposium on Simplicity in Algorithms (SOSA), pages 87–116. Society for Industrial and Applied Mathematics, January 2022. doi:10.1137/1.9781611977066.8.

[bib.bib6] [6] John Canny. Some algebraic and geometric computations in pspace. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC ’88, pages 460–467, New York, NY, USA, 1988. Association for Computing Machinery. doi:10.1145/62212.62257.

[bib.bib7] [7] Alon Efrat and Sariel Har-Peled. Guarding galleries and terrains. Inf. Process. Lett., 100:238–245, January 2006. doi:10.1007/978-0-387-35608-2_16.

[bib.bib8] [8] Aldo Laurentini. Guarding the walls of an art gallery. The Visual Computer, 15:265–278, October 1999. doi:10.1007/s003710050177.

[bib.bib9] [9] D. T. Lee and Arthur K. Lin. Computational complexity of art gallery problems. IEEE Transactions on Information Theory, 32(2):276–282, 1986. doi:10.1109/TIT.1986.1057165.

[bib.bib10] [10] Nikolai E Mnëv. The universality theorems on the classification problem of configuration varieties and convex polytopes varieties. In Topology and geometry—Rohlin seminar, pages 527–543. Springer, 1988.

[bib.bib11] [11] Joseph O’Rourke. Art gallery theorems and algorithms, volume 57. Oxford New York, NY, USA, 1987.

[bib.bib12] [12] Marcus Schaefer and Daniel Stefankovic. Fixed points, nash equilibria, and the existential theory of the reals. Theory of Computing Systems, 60:172–193, 2017. doi:10.1007/S00224-015-9662-0.

[bib.bib13] [13] Marcus Schaefer and Daniel Štefankovič. Beyond the existential theory of the reals. Theor. Comp. Sys., 68(2):195–226, December 2023. doi:10.1007/s00224-023-10151-x.

[bib.bib14] [14] Peter W. Shor. Stretchability of pseudolines is np-hard. In Applied Geometry And Discrete Mathematics, 1990.

[bib.bib15] [15] Jack Stade and Jamie Tucker-Foltz. Topological Universality of the Art Gallery Problem. In Erin W. Chambers and Joachim Gudmundsson, editors, 39th International Symposium on Computational Geometry (SoCG 2023), volume 258 of Leibniz International Proceedings in Informatics (LIPIcs), pages 58:1–58:13, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.SoCG.2023.58.

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

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

1.1 Art gallery problem

1.2 The complexity class ∃ℝ

1.3 Art gallery variants

Definition 1.

1.4 Our results

Theorem 2.

2 ETR-INV-REV

Definition 3.

Definition 4.

Theorem 5.

Theorem 6.

3 Arranging the art gallery

3.1 Creating guard regions

Lemma 7.

Proof.

3.2 Constraint nooks

3.3 Schematic of the art gallery

4 Construction of the copy nooks

4.1 Verifying a single copy nook

Lemma 8.

Proof.

Lemma 9.

5 The constraint gadgets

Lemma 10.

Proof.

Lemma 11.

Proof.

5.1 Inversion gadgets

Lemma 12.

Proof.

Lemma 13.

Proof.

Lemma 14.

Proof.

Lemma 15.

5.2 Addition gadgets

Lemma 16.

Proof.

Lemma 17.

5.3 Final verification

Lemma 18.

Proof.

6 Conclusions

References

The Point-Boundary Art Gallery Problem Is $\exists\mathbb{R}$ -Hard

1.2 The complexity class $\exists\mathbb{R}$