The Point-Boundary Art Gallery Problem is R-hard Jack Stade1 1University of Copenhagen Denmark

2025-05-06 0 0 1.45MB 33 页 10玖币

侵权投诉

The Point-Boundary Art Gallery Problem is ∃R-hard

Jack Stade1

1University of Copenhagen, Denmark

April 2025

Abstract

We resolve the complexity of the point-boundary variant of the art gallery problem, show-

ing that it is ∃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 conﬁguration 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 ∃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 ∃R-hard.

Our techniques can also be used to greatly simplify the proof of ∃R-hardness of the point-

point art gallery problem. The gadgets in previous work could only be constructed by using a

computer to ﬁnd complicated rational coordinates with speciﬁc algebraic properties. All of our

gadgets can be constructed by hand and can be veriﬁed with simple geometric arguments.

Contents

1 Introduction 3

1.1 Artgalleryproblem .................................... 3

1.2 The complexity class ∃R.................................. 3

1.3 Artgalleryvariants..................................... 3

1.4 Ourresults ......................................... 4

2 ETR-INV-REV 4

3 Arranging the art gallery 6

3.1 Creatingguardregions................................... 6

3.2 Constraintnooks ...................................... 7

3.3 Schematic of the art gallery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

4 Construction of the copy nooks 8

4.1 Verifying a single copy nook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

4.2 Arranging all the copy nooks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

arXiv:2210.12817v3 [cs.CG] 10 Apr 2025

5 The constraint gadgets 17

5.1 Inversiongadgets...................................... 18

5.2 Additiongadgets ...................................... 24

5.3 Finalveriﬁcation ...................................... 31

6 Conclusions 32

1 Introduction

1.1 Art gallery problem

The original form of the art gallery problem (AGP) presented by Victor Klee (see O’Rourke [12])

asks whether a simple polygonal region Pcan be guarded by nguards. That is, whether there is a

set of npoints (called the guards) in Psuch that every point in Pis visible to some guard, meaning

that the the line segment between that point and that guard is contained in P. The polygon Pis

referred to as the art gallery.

The vertices of Pare usually restricted to rational or integer coordinates, but even so an

optimal conﬁguration 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 conﬁgurations, only to determine how

many guards are necessary.

It is non-trivial to see that the problem is even decidable. The ﬁrst 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 ∃R

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

∃X1. . . ∃XnΦ(X1, . . . , Xn)

is true, where the Xiare real variables and Φ is a formula in the Xiinvolving 0, 1, +, −,·, =,

<,≤,¬,∧, and ∨. The complexity class ∃Rconsists of problems that can be reduced to ETR

in polynomial time. A number of interesting problems have been shown to be complete for ∃R,

including for example packing polygons in a square [3] and the problem of deciding whether there

exists a point conﬁguration with a given order type [11, 15].

By a result of Schaefer and Stefankovic [13], the exact inequalities used don’t matter; for example

we obtain an equivalent deﬁnition of ∃Rif we don’t allow =, ≤, or ¬in Φ. The same authors have

more recently shown that similar results hold at every level of a real hierarchy, of which ∃Ris the

ﬁrst level [14].

It is straightforward to show that NP ⊆ ∃R. It is also known, though considerably more diﬃcult

to prove, that ∃R⊆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]:

Deﬁnition 1.1. (Agrawal, Knudsen, Lokshtanov, Saurabh, and Zehavi [4]) The X-Y Art Gallery

problem, where X, Y ∈ {Vertex,Point,Boundary}, asks whether the polygon Pcan be guarded

with nguards, where if X= Vertex the guards are restricted to lie on the vertices of the polygons,

if X= Boundary the guards are restricted to lie on the boundary of the polygon, and if X= Point

then the guards can be anywhere inside the polygon. The region that must be guarded is determined

by Yanalogously.

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

If Xor Yis 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

Variant Complexity Lower Bound Complexity Upper Bound

Vertex-Y NP[9] NP

X-Vertex NP[9] NP

Point-Point ∃R[2] ∃R[2]

Boundary-Point ∃R[2] ∃R[2]

Point-Boundary ∃R[this paper] ∃R[2]

Boundary-Boundary NP[9] ∃R[2]

Table 1: Variants of the art gallery problem

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 ∃Rcomplete. It is straightforward

to extend their proof of membership in ∃Rto any of these variants, but they list ∃Rhardness 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 1.2. The point-boundary variant of the art gallery problem is ∃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 ∈ {Vertex,Point,Boundary}.

Our ideas can also be used to considerably simplify the construction in [2]. Both the construction

and veriﬁcation 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 speciﬁed by a simple set of geometric properties rather than by exact

coordinates. Our gadgets are quite ﬂexible and the geometry could probably be adapted to other

settings.

Our reduction is from a problem called ETR-INV-REV, which is a slight modiﬁcation of a

problem ETR-INV from [2]. In Section 2, we deﬁne this problem and show that it is ∃R-hard.

Given an instance Φ of ETR-INV-REV, we show how to construct a polygon whose boundary

can be guarded by some number nguards if and only if Φ 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 1.2.

2 ETR-INV-REV

The proof of Theorem 1.2 is by reduction of the problem we call ETR-INV-REV to the point-

boundary variant of the art gallery problem.

Deﬁnition 2.1. (ETR-INV-REV) In the problem ETR-INV-REV, we are given a set of real vari-

ables {x1, . . . , xn}and a set of inequalities of the form:

x= 1, xy ≥1, x 5

2−y≤1, x +y≤z, x +y≥z,

for x, y, z ∈ {x1, . . . , xn}. The problem asks whether there is an assignment of the xisatisfying

these inequalities with each xi∈[1

2,2].

Abrahamsen, Adamaszek and Miltzow [2] proved the ∃R-hardness of the point-point and boundary-

point variants using a similar problem called ETR-INV.

Deﬁnition 2.2. (Abrahamsen, Adamaszek and Miltzow [2]) (ETR-INV) In the problem ETR-INV,

we are given a set of real variables {x1, . . . , xn}and a set of equations of the form:

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

for x, y, z ∈ {x1, . . . , xn}. The problem asks whether there is a solution to the system of equations

with each xi∈[1

2,2].

Theorem 2.3. (Abrahamsen, Adamaszek, Miltzow [2]) The problem ETR-INV is ∃R-complete.

Regardless of the speciﬁc art gallery variant, it seems to be diﬃcult to make a construction that

admits both xy ≤1 and xy ≥1 constraints. The xy ≤1 inversion gadget in [2] is actually closer

to a x5

2−y≤1 gadget, and another gadget is used to compute a constraint like y′=5

2−y.

By reducing from ETR-INV-REV instead, our construction avoids the need for a reversing gadget.

Theorem 2.4. The problem ETR-INV-REV is ∃R-hard.

Proof. For a variable x, we will show how to construct some additional variables, including a variable

V, as well as some constraints that can only be satisﬁed if V=5

2−x. These constraints should

also be satisﬁable for any value of x∈Ifor some interval Iof length at most 1 (the constraints

depend on the choice of interval I).

Miltzow and Schmiermann [10] show that the addition and constant constraints are suﬃcient

to construct a variable equal to any rational number in [1

2,2]. We will describe the construction for

I= [1,2], and the constraints for any other interval can be obtained by translating.

Using the construction from [10], we construct variable with values 3

2and 5

2. We also add

variables V1,V2,V3and Vand the following constraints:

V1+V1=xV1=1

2x∈[1

2,1]

V1+V2=3

2V2=3

2−1

2x∈[1

2,1]

V3=V2+V2(V3= 3 −x∈[1,2])

V+1

2=V3V=5

2−x∈[1

2,3

2]

Examining the proof of ∃R-hardness of ETR-INV in [2], we can see that it produces instances of

ETR-INV with the following property: every time a xy = 1 constraint appears, there is an interval

Iof length at most 1 such that x∈Iin any satisfying assignment of the instance. The interval Iis

always one of [ 8

15 ,8

13 ],[8

7,8

5] or [65

64 ,105

64 ] (and is known when each xy = 1 constraint is constructed).

Starting with such an ETR-INV instance Φ, we construct an ETR-INV-REV instance Ψ. For

each x+y=zconstraint in Φ, we put constraints x+y≤zand x+y≥zin Ψ. For each xy = 1

constraint, we add constraints xy ≥1 and y5

2−V≤1 for Vconstructed as above.

Ψ has a satisfying assignment if and only if Φ does. This reduction can be performed in

polynomial time, so ETR-INV-REV is ∃R-hard.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

ThePoint-BoundaryArtGalleryProblemis∃R-hardJackStade11UniversityofCopenhagen,DenmarkApril2025AbstractWeresolvethecomplexityofthepoint-boundaryvariantoftheartgalleryproblem,show-ingthatitis∃R-complete,meaningthatitisequivalentunderpolynomialtimereductionstodecidingwhetherasystemofpolynomialequationsh...

展开>> 收起<<

The Point-Boundary Art Gallery Problem is R-hard Jack Stade1 1University of Copenhagen Denmark.pdf

共33页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

The Point-Boundary Art Gallery Problem is R-hard Jack Stade1 1University of Copenhagen Denmark

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: