applied
sciences
Article

Lower Bound for Sculpture Garden Problem: Localization of
IoT Devices
Marzieh Eskandari 1, *,† , Bahram Sadeghi Bigham 2,3, *,†
1
2

3
4

*
†

and Mazyar Zahedi-Seresht 4, *,†

Department of Computer Science, New Jersey Institute of Technology, Newark, NJ 07102, USA
Department of Computer Science, Faculty of Mathematical Sciences, Alzahra University,
Tehran 1993893973, Iran
Institute for Advanced Studies in Basic Sciences (IASBS), Zanjan 45137-66731, Iran
Department of Quantitative Studies, University Canada West, Vancouver, BC V6Z 0E5, Canada
Correspondence: Marzieh.eskandari@njit.edu (M.E.); b_sadeghi_b@alzahra.ac.ir or
b_sadeghi_b@iasbs.ac.ir (B.S.B.); mazyar.zahedi@ucanwest.ca (M.Z.-S.)
Authors contributed equally to this work and the Authors’ name are in alphabetical order.

Abstract: The purpose of the current study is to investigate a special case of art gallery problem,
namely a sculpture garden problem. In this problem, for a given polygon P, the ultimate goal is
to place the minimum number of guards (landmarks) to define the interior polygon P by applying
a monotone Boolean formula composed of the guards. Using this problem, it can replace the
operation-based method with time-consuming, pixel-based algorithms. So, the processing time of
some problems in the fields of machine vision, image processing and gamification can be strongly
reduced. The problem has also many applications in mobile device localization in the Internet of
Things (IoT). An open problem in this regard is the proof of Eppstein’s conjecture, which has remained
an open problem since 2007. According to his conjecture, in the worst case, n − 2 vertex guards are
required to describe any n-gon. In this paper, a lower bound is introduced for the special case of this
problem (natural vertex guard), which shows that if a polygon can be defined with natural vertex
guards, then n − 2 is a lower bound.
Keywords: art galley; Boolean formula; computational geometry; prison yard problem; sculpture
garden problem; IoT
Citation: Eskandari, M.; Sadeghi
Bigham, B.; Zahedi-Seresht, M.
Lower Bound for Sculpture Garden

MSC: 68Q25; 68U05; 52Cxx

Problem: Localization of IoT Devices.
Appl. Sci. 2023, 13, 2597. https://
doi.org/10.3390/app13042597
Academic Editors: Liang-Bi Chen
and Tian-Hsiang Huang
Received: 25 January 2023
Revised: 15 February 2023
Accepted: 15 February 2023
Published: 17 February 2023

Copyright: © 2023 by the authors.
Licensee MDPI, Basel, Switzerland.
This article is an open access article
distributed under the terms and
conditions of the Creative Commons

1. Introduction
A large and growing body of literature about computational geometry has explored
the art gallery problem. The main goal in this problem is to find the minimum number of
point guards inside a polygon (P) such that the set of guards can see the whole P. Each
guard can see its surroundings in 360 degrees and up to infinity (if there are no obstacles).
The number of guards that suffices and is sometimes necessary for any arbitrary polygon
with n vertices is bn/3c [1]. The main goal in our study is to find the minimum set of
angle guards by which the geometry of the polygon can be defined through two operations,
AND (.) and OR(+). An angle guard g views an infinite wedge of the plane (by going
through the involved obstacles) and can be defined as a Boolean predicate, Bg ( p), which is
True for a given point, p ∈ P, if p is inside the view region of g, otherwise it is False. Given
a polygon P, the aim is to place a set of angle guards on P in such a way that the monotone
Boolean formula FP ( p) is True, if and only if p is inside P or on the boundary of polygon P
(p ∈ ∂P), otherwise it is False:

Attribution (CC BY) license (https://
creativecommons.org/licenses/by/
4.0/).

Appl. Sci. 2023, 13, 2597. https://doi.org/10.3390/app13042597


FP ( p) =

True
False

if p ∈ P or p ∈ ∂P
otherwise

https://www.mdpi.com/journal/applsci

Appl. Sci. 2023, 13, 2597

2 of 16

There are several applications in machine vision, image processing and gamification
which require the range of a shape to be determined. Various algorithms for these problems
have been presented that are based on pixels, area, vertices and so on. These methods
require a lot of processing time in problems that require fast processing (such as computer
games and graphics). Even these methods force users to provide more powerful hardware
to run a machine vision system or computer game. The method discussed in this paper
is related to a problem that uses only a few points, angles and two logical operators to
determine the range of a shape. Using this method, various applications in machine vision
and computer games are performed much faster and with a lower number of operations.
An angle guard vertex placement is considered as natural if all the guards of P have the
same view of their corresponding vertices [2]. As Eppstein et al. stated, a polygon P can be
demonstrated in a way that a natural angle guard vertex placement cannot fully distinguish
between points on the inside and outside of P which implies that Steiner-point guards are
sometimes necessary [2]. According to Figure 1a, even the placement of a natural angle at
every vertex of the pentagon is not able to distinguish between the points x and y and at
least one unnatural guard is needed to define the polygon (Figure 1b). Consequently, the
polygon is defined by F = A.B.D.
A variety of cases of the problem is present in which the location and angle of view of
the guards are different. We focus on a type of the problem that all the guards are placed on
the vertices of P. It was a conjecture [3] that in the worst case, n − 2 guards are needed to
describe an n-gon. In this paper, we present an algorithm to generate a polygon for a given
n which needs at least n − 2 natural vertex guards. We do not prove Eppstein’s conjecture
and this problem is still open. However, by using our algorithm, we create an n-gon for
any given n, which needs exactly n − 2 natural vertex guards.
In the next section, the sculpture garden problem is introduced and some applications
are mentioned. Section 3 provides the main problem and presents an algorithm for generating the n-gon which needs exactly n − 2 natural vertex guards to be defined. Finally,
Section 4 presents the findings of the study and also some suggestions for further research.

Figure 1. (a) Natural angle guards do not suffice to define the polygon; (b) coverage by three guards
(formula B.C.D define the polygon) [3].

2. Sculpture Garden Problem and Applications
As mentioned previously, the sculpture garden problem can be considered as a special
case of an art gallery problem. There are various problems with similarities and differences
with the sculpture garden problem. As the sculpture garden problem comes up from
localization problems in wireless mobile computing, we wish to determine the position of
some devices in a geometric environment.
The sculpture garden problem could be used in localization problems in which a
wireless device is used to prove that it belongs to a given polygonal environment. In this
case, the locators would be simple and can broadcast information inside a certain angle.
In this context, the Boolean predicates could be associated with secret keys. Therefore,
each angle guard g could periodically broadcast a secret key K in its transmission angle

Appl. Sci. 2023, 13, 2597

3 of 16

and consequently the devices in range would have knowledge of this key. The wireless
localization problem with natural vertex guards is an NP-hard problem [4,5].
In another application, namely constructive solid geometry (CSG), we wish to construct a geometric shape from simple combinations of primitive shapes [6]. Solutions to the
sculpture garden problem can be used to construct an efficient CSG formula that defines a
given polygon P. The prison yard problem seeks a set of guards that can simultaneously
see both the interior and exterior of a simple polygon, in which bn/2c guards are sufficient
and sometimes necessary (tight bound) [7]. Another related problem is the floodlight
illumination problem, in which the vertex angle guards (called floodlights) with angles
of 180 should see a simple polygon [8]. Likewise, studies have been conducted on the
complexity of illuminating wedges with angle-restricted floodlights placed at a fixed set
of points [9]. There is another study on a generalization of the classical problem of the
illumination of polygons. Aichholzer et al. [10] modeled a wireless device whose radio
signal can penetrate a given number k of walls (k-modems) and they studied the minimum number of k-modems sufficient and sometimes necessary to illuminate monotone
and monotone orthogonal polygons. They showed that every monotone polygon with n
n −2
vertices can be illuminated with d 2k
+3 e k-modems. Ballinger et al. [11] developed lower
and upper bounds for the number of k-transmitters that are necessary and sufficient to
cover a given collection of line segments, polygonal chains and polygons.
In one of the applications of the problem, the wireless localization problem is considered to deal with the placement of the smallest number of broadcasting antennas required
to satisfy some property within a given polygon. The antennas propagate a unique key
within a certain antenna-specific angle of broadcast, so that the set of keys received at any
given point is sufficient to determine whether that point is inside or outside the polygon.
To ascertain this localization property, a Boolean formula must be produced along with
the placement of the antennas. Crepaldi et al. [12,13] presented an exact algorithm based
on integer linear programming for solving the NP-hard natural wireless localization problem. Cano et al. [14] show that dn/2e point guards are always sufficient and sometimes
necessary to guard a piecewise convex art gallery with n vertices. Karavelas et al. [15,16]
showed that for monitoring a piecewise-convex polygon with n ≥ 2 vertices, b 2n
3 c vertex
guards are always sufficient and sometimes necessary. They also presented a polynomial
algorithm for computing the location of guards.
Since we are interested in more than simply observing the inside and outside of
a polygon, solutions to the art gallery or prison yard problems would not change into
solutions to the sculpture garden problem. In other words, we intend to establish the time
when a point is inside a polygon using only the guards as witnesses.
Indeed, any polygon P can be triangulated and two angle guards can be used to define
each of the resulting n + 2(h − 1) triangles, where h is the number of holes in P. This would
give rise to a concise formula F defining P. However, it uses at least 2n + 4(h − 1) angle
guards, which is a more constant-depth formula.
Upper and Lower Bounds
The sculpture garden problem has different types due to the different restrictions as
guards could be observed in varied forms including vertices, edges, interior or exterior of
the polygon, and the SGP can be manifested in different types as well. However, in each
case, finding the upper and lower bound is a problem that has already been investigated.
An angle guard g with angle α ∈ (0, 360) is a pair ( a, ωα ) of a point a and an infinitive
wedge ωα of aperture α at apex a and views ωα . It can be shown as a Boolean predicate
Bg ( p), in which for a point p in the plane, Bg ( p) is True if p is inside the angle associated
with g, otherwise it is False. Given a polygon P with n vertices, we intend to allocate the
minimum number of angle guards with arbitrary angles at vertices of P. Thus, a monotone
Boolean formula, FP (.), based on the angle guard predicates, Bg (.), is obtained as follows:

Appl. Sci. 2023, 13, 2597

4 of 16


FP ( p) =

True
False

∀ p ∈ int( P)
otherwise

(1)

It is worth mentioning that int( P) is the interior of polygon P. If FP ( p) is a solution
of the sculpture garden problem for a given P, P is defined by FP . The complement of an
angle guard g = ( a, ωα ) is an angle guard g0 at the point a with angle 2π − α. Hence, the
wedge associated with g0 is the complement of ωα in the plane. If formula F is a solution for
the sculpture garden problem for polygon P, then the complement of F which is denoted
by F 0 defines the exterior of P. To obtain F 0 , initially, we replace every angle guard g by
its complement, (i.e., g0 ), and then swap the operations AND and OR. In addition, we
define , a pocket of a simple polygon as the areas outside of the polygon and inside of its
convex hull.
As Eppstein et al. [2,3] reported, for any polygon P, a set of n + 2(h − 1) angle guards
and an associated concise formula F are present, solving the sculpture garden problem
where h is the number of holes in P. So, a simple polygon can be defined with n − 2 guards.
They have conjectured a class of simple n-gons that require at least n − 2 vertex guards.
The main goal of this paper is to solve a special case of this open problem for natural vertex
guards. They showed that at least dn/2e guards are required to solve the sculpture garden
problem for any polygon with no two edges lying on the same line. Furthermore, for any
convex polygon P, a natural angle guard vertex placement is present whose dn/2e guards
are sufficient. They showed that dn/2e + O(1) angle guards suffice to solve the sculpture
garden problem for pseudo-triangles. Moreover, for any orthogonal polygon P (which
is probably the most likely real-world application), a set of b3(n − 2)/4c angle guards
and an associated concise formula F are available to solve the sculpture garden problem
using dn/2e natural angle guards. They gave an example
of a class of simple polygons
√
containing sculpture garden solutions that used O( n) guards. Afterwards, they showed
that the bound is optimal. On the contrary, some varied results are obtained for vertex
guards. As Damian et al. demonstrated [17], a class of simple n-gons are presented that
require at least b2n/3c − 1 guards placed at polygon vertices for localization. Through
revealing the point that the maximum number of guards to describe any simple polygon on
n vertices is roughly observable at (3/5n, 4/5n), Hoffman et al. enhanced both upper and
lower bounds for the general setting [18]. Eskandari et al. [19] improved the large upper
bound n + 2(h − 1) for an arbitrary n-gon with h holes for placing guards and obtained a
tight bound (n − dc/2e − h), where c is the number of vertices of convex hull of P. So, in
simple polygons, this bound is n − dc/2e, which is tight too. To complete the first column
of Table 1, a new class of polygons entitled Helix is introduced in the next section. In some
previous documents, this type of polygon was called spiral polygon.
Table 1. Number of guards needed for a simple polygon with n vertices.
Natural Vertex

Natural

Vertex

General

b (4n5−2) c [18]
d (3n5−4) e [18]

U pperBound

Unknown

n − 2 [18]

Unknown

LowerBound

Unknown

n − 2 [18]

)
b (2n
3 c − 1 [17]

3. Helix Polygon
In this section, we explore the special class of the sculpture garden problem, where
the guards are natural. We demonstrate the point that the lower bound for the problem is
n − 2. To do so, we commence with introducing a class of polygons demanding the exact
number of n − 2 natural guards to be defined. In the next section, we introduce this class of
polygons named Helix (see Figure 2).

Appl. Sci. 2023, 13, 2597

5 of 16

Figure 2. (a) A Helix with 11 vertices. (b) A Helix with 12 vertices.

3.1. Construction of Helix
An n-gon Helix polygon (i.e., Hn ) is constructed by an incremental method using an
n − 1-gon Helix, Hn−1 . A Helix with three vertices is a triangle. By adding two new edges
to Hn−1 and also removing an edge of Hn−1 , Hn is constructed on the basis of Hn−1 , where
n ≥ 4. The details are presented in Algorithm 1 and are illustrated in Figure 3.
Algorithm 1 Constructing Helix Polygon
Input: Integer number n ≥ 3 as the number of vertices.
Output: The Helix polygon Hn .
1: Construct H3 = 4v1 v2 v3 , which is an equilateral triangle, where v2 v3 is horizontal and
the vertices are in counterclockwise order.
| v2 v3 |
2: Choose a positive real number δ so 0 < δ <
1
2b n −
3 c
3: p1 = v1 ; p2 = v2 ; p3 = v3 .
4: for i = 4; i ≤ n; i + + do
5:
q1 = p1 ; p1 = a point on v1 v2 such that | p1 q1 | = δ, a = l13 ( p1 );
6:
q2 = p2 ; p2 = a point on v2 v3 such that | p2 q2 | = δ, b = l12 ( p2 );
7:
q3 = p3 ; p3 = a point on v1 v3 such that | p3 q3 | = δ, c = l23 ( p3 );
8:
if i == 4 then
9:
l = b;
10:
else
11:
l = l24 (vi−2 );
12:
end if
13:
if i 0 == 5 then
14:
l = c;
15:
else0
16:
l = l35 (vi−2 );
17:
end if
18:
if i == 3k then
19:
vi = a ∩ c;
20:
end if
21:
if i == 3k + 1 then
22:
vi = c ∩ l;
23:
end if
24:
if i == 3k + 2 then
0
25:
vi = b ∩ l ;
26:
end if
27:
Add edges vi vi−1 and vi vi−2 .
28:
Remove vi−1 vi−2 to obtain Hi
29: end for
30: Return Hn .
It is worth noting that the length of a line segment pq is denoted by | pq|, and for an
arbitrary point p, lij ( p) denotes a line parallel to vi v j which passes through p.

Appl. Sci. 2023, 13, 2597

6 of 16

Figure 3. Final step of Algorithm 1 for generating H12 .

3.2. Properties of Helix
Constructing the Helix polygon sheds light on the fact that for i > 2, the angles made
by vertices v2i are concave and for i > 0 , vertices v2i+1 and v2 are convex (Figure 2).
In fact, the pocket of a polygon P is defined as CH ( P) − P where CH ( P) is the convex
hull of the vertices of P. The pocket of a Helix polygon with n vertices is a Helix polygon
with n − 1 vertices (Figure 4). The pocket of a polygon Hn is denoted by P( Hn ). For i,
0
0
1 ≤ i ≤ n − 1, the vertices of P( H ) are called v , located on v . For n > 4, the angle vb in
n

i

i +1

P( Hn ) is obtained as follows:

 v\
1 v2 v3 − v\
1 v2 v4
0
b
vi =
v\
v v − v\
1 v3 v5
 1 3 2
2π − interior angle of vi+1 in Hn

i=1
i=2
i ≥ 3.

Figure 4. (a) Helix H12 . (b) Pocket of H12 which is a Helix with 11 vertices.

i

(2)

Appl. Sci. 2023, 13, 2597

7 of 16

We will show that polygon Hn for any given natural number n[3), can be defined by
n − 2 natural vertices guards which are located on v1 , v2 , . . . , vn−3 , vn . The Boolean formula,
Fn , is as below:
dn/2e−2

∑

Fn =

Ai .g2i + Abn/2c−1 .gn

(3)

i =1

where A1 = g1 , Ai+1 = Ai .g2i+1 for all 1 ≤ i ≤ bn/2c − 2 and gi is the natural vertex guard
located on the vertex vi of Hn . To clarify this point, F8 can be written as follows:
2

F8 = ∑ Ai .g2i + A5 .g8

(4)

i =1

where A1 = g1 , A2 = g1 .g3 and A3 = g1 .g3 .g5 . Thus, we have
F8 = g1 .g2 + g1 .g3 .g4 + g1 .g3 .g5 .g8
Generally, we expand Fn as follows:
(
Fn =

1
k −2
∑ik=−11 (∏ij−
=0 g2j+1 ).g2i + ( ∏ j=0 g2j+1 ).gn
1
k −1
∑ik=−11 (∏ij−
=0 g2j+1 ).g2i + ( ∏ j=0 g2j+1 ).gn

n = 2k + 1, k ∈ N
n = 2k + 2, k ∈ N.

(5)

According to Lemma 1, Fn defined by Equation (5) describes Hn .
Lemma 1. Helix polygon Hn can be defined by n − 2 natural vertex guards gi (1 ≤ i ≤ n; i 6=
n − 1, n − 2) located on v1 , v2 , . . . vn−3 , vn and the correspondent Boolean formula is Formula 5.
Proof. We will prove the lemma by induction. When n = 3, k = 1 and F3 = g1 .g3 clearly
define triangle H3 . For n = 4, k = 1 and F4 = g1 .g4 define H4 and it implies that Lemma 1
holds for n = 3, 4. Now, for n ≥ 5, without loss of generality, assume that n = 2k + 2, k ∈ N.
According to Property 2, P( Hn ) is a Helix polygon with 2k + 1 vertices. By induction
hypothesis, P( Hn ) can be defined as follows:
k −1 i −1

k −2

i =1 j =0

j =0

0
0
0
0
F 0 = ∑ ( ∏ g2j
+1 ).g2i + ( ∏ g2j+1 ).g2k+1

(6)

where gi0 is a natural guard on the vertex vi0 of P( Hn ). According to correspondence between
the vertices of Hn and P( Hn ), we have
gi0 =



gic+1
Gi+1 .gic+1

i≥3
i = 1, 2.

(7)

in which gc is the complement of guard g and G2 and G3 are the guards located on v2 and
v3 with the angles v\
1 v2 v3 and v\
1 v3 v2 , respectively. So, we have
k −1 i −1

k −2

i =2 j =0

j =0

0
0
0
0
F 0 = g10 .g20 + ∑ ( ∏ g2j
+1 ).g2i + ( ∏ g2j+1 ).g2k+1
k −1

i −1

k −2

i =2

j =1

j =1

0
0
0
0
0
= g10 .g20 + ∑ g10 .(∏ g2j
+1 ).g2i + g1 .( ∏ g2j+1 ).g2k+1
k −1

i −1

k −2

i =2

j =1

j =1

c
c
c
c
c
= G2 .G3 .g2c .g3c + ∑ G2 .g2c .(∏ g2j
+2 ).g2i +1 + G2 .g2 .( ∏ g2j+2 ).g2k+2

Appl. Sci. 2023, 13, 2597

8 of 16

k −1 i −1

k −2

i =2 j =0

j =0

c
c
c
c
= G2 .[ G3 .g2c .g3c + ∑ (∏ g2j
+2 ).g2i +1 + ( ∏ g2j+2 ).g2k+2 ]
k −1 i −1

k −2

i =2 j =0

j =0

=⇒ ( F 0 ) = G2c + ( G3c + g2 + g3 ).( ∏ ( ∑ g2j+2 ) + g2i+1 ).( ∑ g2j+2 + g2k+2 )
c

0 c

c

Consider the point that F = ( g1 .g2 ).( F ) + ( g1 .g3 ).( F 0 )c . By replacing ( F 0 ) from the
above relation, we obtain
k −1 i −1

k −2

i =2 j =0

j =0

F = g1 .( g2 + g2 .g3 ).( ∏ ( ∑ g2j+2 ) + g2i+1 ).( ∑ g2j+2 + g2k+2 )
k −1 i −1

k −2

i =2 j =0

j =0

+ g1 .( g2 .g3 + g3 ).( ∏ ( ∑ g2j+2 ) + g2i+1 ).( ∑ g2j+2 + g2k+2 )
Note that g1 .g2 .G2c = g1 .g3 .G2c = g1 .g2 .G3c = g1 .g3 .G3c = ∅. So, we have
k −1 i −1

k −2

i =2 j =0

j =0

F = ( ∏ ( ∑ g2j+2 ) + g2i+1 ).( ∑ ( g2j+2 + g2k+2 )).( g2 + g3 ).g1
Now, we show that F can define Hn which contains exactly the natural guards
g1 , g2 , . . . , gn−3 , gn and can be written in the form of Fn .
First, consider the definition of F which contains only natural guards. To prove that
Hn can be defined by F, let x be an arbitrary point inside Hn . We have g1 ( x ) = True and
( F 0 )c ( x ) = True ( x ∈ Hn =⇒ x ∈
/ P( Hn ) =⇒ F 0 ( x ) = False =⇒ ( F 0 )c ( x ) = True ).
There are two cases:
•
•

g2 ( x ) = True =⇒ F ( x ) = ( g1 ( x ).g2 ( x )).( F 0 )c ( x ) + ( g1 ( x ).g3 ( x )).( F 0 )c ( x ) = True
g2 ( x ) = False =⇒ g3 ( x ) = True =⇒ ( g1 ( x ).g3 ( x )).( F 0 )c ( x ) = True =⇒ F ( x ) =
True.
Thus, F can distinguish the interior of Hn . Now, let x ∈
/ Hn . There are two cases:

•
•

x ∈ P( Hn ) =⇒ F 0 ( x ) = True, ( F 0 )c ( x ) = False =⇒ F ( x ) = False
x∈
/ P( Hn ) =⇒ x ∈ Ext(4v1 v2 v3 ) =⇒ g1 ( x ) = False =⇒ F ( x ) = False.

So, F can distinguish the exterior of Hn as well. Now, we show that F can be written
in the form of Fn . Let
k −1 i −1

k −2

i =2 j =0

j =0

S = ( g2 + g3 ).( ∏ ( ∑ g2j+2 ) + g2i+1 ).( ∑ g2j+2 + g2k+2 )
and

k −1 i −1

k −1

i =1 j =1

j =1

T = ∑ ( ∏ ( g2j+1 ).g2i ) + ( ∏ ( g2j+1 ).g2k+2 )
Note that Fn = g1 .T and F = g1 .S. To prove F = Fn , it is sufficient to show that T = S.
(r )

For all integers r where 1 ≤ r ≤ k − 1, we define Si
(
(r )
Si =

1
g2i+1 + ∑ij−
=r g2j+2

as follows:
r ≤ i ≤ k−1

−2
g2k+2 + ∑kj=
r g2j+2

i = k.

1
g2i+1 + ∑ij−
=1 g2j+2

1 ≤ i ≤ k−1

(8)

So, we have
(
(1)
Si =

−2
g2k+2 + ∑kj=
1 g2j+2

i = k.

(9)

Appl. Sci. 2023, 13, 2597

9 of 16

(r )

By definition of Si , it is clear that
k

k

S = ∏ ( g2 + S i ) = g2 + ∏ S i
(1)

i =1

(r )

(r +1)

− Si

On the other hand, Si

k

i =1

= g2r+2 . Therefore we have

∏ Si

(r )

i =r

k

= g2r+1 . ∏ Si

(r )

i =r +1

(1)

k

= Sr . ∏ S i
(r )

(r )

i =r +1

k

= g2r+1 . ∏ ( g2r+2 + Si

(r +1)

i =r +1

k

) = g2r+1 .( g2r+2 + ∏ Si

(r +1)

)

i =r +1

(1)

By applying obtained recursive relation, k − 2 times on S = g2 + ∏ik=1 Si , S = T. In
this respect, we have
k

S = g2 + ∏ S i

(1)

i =1

k

k

= g2 + g3 .( g4 + ∏ Si ) = g2 + g3 .g4 + g3 . ∏ Si
(2)

i =2

(2)

i =2

k

S = g2 + g3 .g4 + g3 .g5 .g6 + g3 .g5 . ∏ Si

(3)

i =3

After t times, we have
t +1 i −1

t

k

i =1 j =1

j =1

i = t +1

k −1 i −1

k −2

k

i =1 j =1

j =1

i = k −1

S = ( ∑ ( ∏ g2j+1 ).g2i ) + ∏ g2j+1 . ∏ Si

( t +1)

So after k − 2 times, we have
( k −1)

S = ( ∑ ( ∏ g2j+1 ).g2i ) + ∏ g2j+1 . ∏ Si
( k −1)

Note that ∏ik=k−1 Si

( k −1)

( k −1)

= Sk−1 .Sk

= g2k−1 .g2k+2 ; therefore,

k −1 i −1

k −1

i =1 j =1

j =1

S = ( ∑ ( ∏ g2j+1 ).g2i ) + ∏ g2j+1 .g2k+2 = T.
S = T implies F = Fn which means that F can be written in the form of Fn and could
define Hn .
3.3. Necessity of n − 2 Natural Vertex Guards for Helix
In this section, we will prove that it is impossible to define a Helix polygon with fewer
than n − 2 natural vertex guards.
Lemma 2. Every arbitrary set of natural vertex guards G which defines Hn contains g1 , a natural
vertex guard on v1 . The final formula is in the form of F = F1 .g1 , where F1 is a Boolean expression
of G − { g1 }.
Proof. Let G be an arbitrary set of natural guards which defines Hn by Boolean formula
F. Suppose for a contradiction that g1 does not belong to G. Since v1 v2 and v1 v3 are
edges of Hn , G should contain two natural guards on v2 and v3 which are called g2 and g3 ,
respectively. So, F can be written in the general form F = g2 .g3 .T1 + g2 .T2 + g3 .T3 where Ti s

Appl. Sci. 2023, 13, 2597

10 of 16

are Boolean formulas which do not contain g1 , g2 and g3 . This will result in a contradiction,
mentioned below.
Consider two regions, R1 and R2 , as shown in Figure 5. Let x be an arbitrary point
inside R1 or R2 . So, we have g2 ( x ) = True and g3 ( x ) = False. So,
F ( x ) = T2 ( x )

(10)

Furthermore, note that we can expand T2 in the following general form:
(1)

T2 = T2

(2)

(l )

+ T2 + . . . + T2

(11)

(i )

where T2 s are the multiplication of some natural guards in G. Let x ∈ R1 be an arbitrary
point. So, from Equation (10), it is implied that
x ∈ R1 =⇒ T2 ( x ) = F ( x ) = True
Therefore, at least one of the expressions of T2 should be True. Without loss of
(1)

(1)

= gi1 .gi2 . · · · .gim , where gi j is the
(1)
natural guards of G and j = 1, 2, 3. Since T2 ( x ) = True, we have
generality, it can be called T2

and is written as T2

∀ j : 1 ≤ j ≤ m : gi j ( x ) = True
Regarding the structure of Hn , none of indices i j can be odd. This is because we know that

∀i ≥ 1 : g2i+1 ( x ) = False
Now, let y ∈ R2 be an arbitrary point. Due to the structure of Hn , it is inferred that for
all ∀y ∈ R2 , we have
∀i ≥ 2 : g2i (y) = True.
(1)

So, T2 ( x ) = True and from Equation (11), T2 (y) = True is obtained and consequently
F (y) = T2 (y) = True (due to Equation (10). Nevertheless, y ∈
/ Hn , which is a contradiction.
With regard to the existence of g1 in G, F can be written in the form of F = g1 .T1 + T2 ,
where T2 does not contain g1 . Indeed, g1 .T1 + g1 .T2 defines Hn as well. Let x ∈ Hn , then
g1 ( x ) = True and g1 ( x ).T1 ( x ) + g1 ( x ).T2 ( x ) = g1 ( x ).T1 ( x ) + T2 ( x ) = F ( x ) = True. If
y∈
/ Hn and g1 (y) = True, then g1 (y).T1 (y) + g1 (y).T2 (y) = g1 (y).T1 (y) + T2 (y) = F (y) =
False. On the other hand, if g1 (y) = False, then g1 (y).T1 (y) + g1 (y).T2 (y) = False. So,
F = g1 .( T1 + T2 ) defines Hn . In other words, F can be expressed as F = g1 .F1 .

Figure 5. Regions R1 and R2 can be distinguishable without the existence of g1 in the formula.

Appl. Sci. 2023, 13, 2597

11 of 16

Lemma 3. Every arbitrary set of natural vertex guards G defining Hn contains g2 (i.e., a natural
guard on v2 ). The final formula is in the form of F = g1 .( g2 + F2 ), where F2 is a Boolean expression
of G − { g1 , g2 }.
Proof. Let G be an arbitrary set of natural guards which defines Hn by Boolean formula F,
for n ≥ 4. Suppose a contradiction in which g2 does not belong to G. From Lemma 2, we
can write
F = g1 .( T1 + T2 + . . . + Tl )
where Ti s are Boolean expression of natural guards of G.
Consider two regions, R1 and R3 , as shown in Figure 6. Let x ∈ R1 be an arbitrary
point. We have F ( x ) = g1 ( x ).( T1 ( x ) + T2 ( x ) + . . . + Tl ( x )) = True. Thus, at least one
of the expressions Ti s is True. Without loss of generality, it can be named T1 and is
written as T1 = gi1 .gi2 . . . .gim where gi j s are some natural guards in G and i j 6= 1, 2. Since
T1 ( x ) = True, we have
∀ j, 1 ≤ j ≤ m : gi j ( x ) = True
Regarding the structure of Hn , i j s are even, because ∀i ≥ 2 : g2i ( x ) = True.
Now, let y ∈ R3 be an arbitrary point. Obviously, ∀i ≥ 2, g2i (y) = True which implies
T1 (y) = True. Then, F (y) = True. However, y ∈
/ Hn , which denotes a contradiction.
In addition, F can be manifested as below:
F = g1 .( g2 .T1 + T2 )
Now note that for all points which are located in the interior (or exterior) of Hn , the
above formula has the same value with the formula g1 .( g2 + T2 ). This fact can be shown
easily by considering all cases. Then, F = g1 .( g2 + F1 ).

Figure 6. Regions R1 and R3 can be distinguishable without the existence of g2 in the formula.

Lemma 4. It is not possible to define H5 with less than 3 natural vertex guards. The formula is
F = g1 . ( g2 + g5 ) .
Proof. Regarding Lemmas 2 and 3, F can be written as g1 .( g2 + F2 ). The edges v4 v5 and
v3 v5 should have at least one guard on their endpoints. The optimal possibility is to locate
a guard on v5 as their intersection point. Clearly, g1 .( g2 .g5 ) defines H5 .

Appl. Sci. 2023, 13, 2597

12 of 16

Lemma 5. Every arbitrary set of natural vertex guards G which defines Hn contains g3 which is a
natural guard on v3 . The final formula is in the form of F = g1 .( g2 + g3 .F3 ) where F3 is a Boolean
expression of G − { g1 , g2 , g3 }.
Proof. Let G be an arbitrary set of natural guards which defines Hn by Boolean formula
F for n ≥ 6. Suppose a contradiction in which g3 does not belong to G. By Lemma 3,
F = g1 .( g2 + F2 ). Assume that F2 = T1 + T2 + . . . + Tl , where Ti s are multiplication of
natural guards in G.
Consider two regions, R3 and R4 , as shown in Figure 7. Let x ∈ R4 be an arbitrary
point. We have F ( x ) = F2 ( x ) = True. So, at least one of Ti s is True. Without loss of
generality, we call it T1 , which can be expressed as follows:
T1 = gi1 .gi2 . . . .gim
where gi j s are natural guards in G and i j 6= 1, 2, 3.
Since T1 ( x ) = True, we have

∀ j, 1 ≤ j ≤ m : gi j ( x ) = True
Therefore, i j s are even. Now, let y ∈ R3 be an arbitrary point. This point casts light
that for all i ≥ 2, g2i (y) = True, which implies T1 (y) = True. Then, F (y) = True. However,
y∈
/ Hn , showing a contradiction. So, g3 ∈ G.
In addition, F can be written as below:
F + g1 .( g2 + g3 .F3 )
It can be easily obtained from equivalency of g1 .( g2 + F2 ) and g1 .( g2 + g3 .F3 ) for all
points with respect to Hn .

Figure 7. Regions R3 and R4 can be distinguishable without the existence of g3 in the formula.

Lemma 6. It is not possible to define H5 with fewer than three natural vertex guards. The formula
is F = g1 .( g2 + g3 .g6 ).
Proof. Considering Lemma 5, H6 can be defined by F = g1 .( g2 + g3 .F3 ). Since v4 v6 and
v6 v5 are two edges of H6 , it is required to place at least one guard on one of the endpoints
of these two edges. The optimal placement is to place a guard on v6 . Obviously, H6 can be
defined by F = g1 .( g2 + g3 .g6 ).

Appl. Sci. 2023, 13, 2597

13 of 16

Lemma 7. Every arbitrary set of natural vertex guards G which defines Hn , for all n ≥ 7, contains
g4 , a natural guard on v4 . The final formula is in the form of F = g1 .( g2 + g3 .( g4 + F4 )), where
F4 is a Boolean expression of G − { g1 , g2 , g3 , g4 }.
Proof. Let G be an arbitrary set of natural guards defining Hn by Boolean formula F and n ≥ 7.
Suppose a contradiction in which g4 does not belong to G. By Lemma 5, F = g1 .( g2 + g3 .F3 ).
It is intended to show that F3 = g4 + F4 . Assume that F3 = T1 + T2 + . . . + Tl , where Ti s are
the multiplication of natural guards of G. Consider two regions, R5 and R6 , shown in Figure 8.
Let x ∈ R5 be an arbitrary point, then F ( x ) = F3 ( x ) = True. So, at least one of Ti s is True.
Without loss of generality, t is called T1 which can be expressed as below:
T1 = gi1 .gi2 . . . .gim
where gi j s are natural guards and i j 6= 1, 2, 3, 4. Since T1 ( x ) = True, for all j : 1 ≤ j ≤ m,
gi j ( x ) = True. Therefore, i j s are even. Now, let y ∈ R6 be an arbitrary point (see Figure 8).
It is clear that for all i ≥ 2, g2i (y) = True, which implies T1 (y) = True. Then, F (y) = True.
However, y ∈
/ Hn , indicating a contradiction. So, g4 ∈ G. In addition, F can be written as below:
F = g1 .( g2 + g3 .( g4 + F4 ))
It can be easily shown that g1 .( g2 + g3 .F3 ) is equivalent with g1 .( g2 + g3 .( g4 + F4 )) for
all the points inside or outside of Hn .

Figure 8. Regions R5 and R6 can be distinguishable without the existence of g4 in the formula.
0

0

0

Lemma 8. Let Hn be defined by F = g1 .( g2 + g3 .( g4 + F4 )). Formula FP = g1 .( g2 + g3 .F4c )
0
defines the pocket of Hn , P( Hn ), where gi s are defined in Equation (7).
Proof. Let x ∈ P( Hn ) and y ∈
/ P( Hn ) be two arbitrary points (see Figure 9). Then, it can be
0
0
demonstrated that FP ( x ) = True and FP (y) = False. Additionally, g2 = G3 .g3c and g3 = g4c ,
0
so x ∈ P( Hn ) =⇒ g1 ( x ) = True and G3 ( x ) = True. So
FP ( x ) = g3c ( x ) + g4c ( x ).F4c ( x )

(12)

On the other hand, x ∈ P( Hn ) implies that F ( x ) = False and g1 ( x ) = True. Hence,
F ( x ) = g2 ( x ) + g3 ( x ).( g4 ( x ) + F4 ( x )) = False =⇒ g3 ( x ).( g4 ( x ) + F4 ( x )) = False.

Appl. Sci. 2023, 13, 2597

14 of 16

So,
g3c ( x ) + g4c ( x ).F4c ( x ) = True

(13)

From Equations (12) and (13), FP ( x ) = True can be obtained.
0
If g (y) = False, for y ∈
/ P( Hn ), FP (y) = False and the process of our calculations has
0
0
been completed. Assume that g (y) = True, then as y ∈
/ P( Hn ), consequently g2 (y) =
0
0
False (see Figure 9). If g3 (y) = False, FP (y) = False. Now, suppose that g3 (y) = True
(i.e., g4 (y) = False). This assumption implies that y ∈ Hn and we have g1 (y) = True,
g2 (y) = False, g3 1(y) = True and g4 (y) = False. Since y ∈ Hn , F( y) = F4 (y) and
consequently, F4 (y) = True. So, we have FP (y) = False. This means that FP defines
P( Hn ).

Figure 9. Natural vertex guards for packet of Helix.

Theorem 1. Hn requires at least n − 2 natural vertex guards.
Proof. We prove this theorem by induction. It is clear that for n = 4, H4 is a tetragon and
cannot be defined by fewer than two guards. We proved this in corollaries 4 and 6 for n − 5.
Now, assume that this holds for n − 1, and we have to prove it for n where n ≥ 7. Let F be
a Boolean formula which defines Hn . With regard to Lemma 7, F = g1 .( g2 + ( g3 .( g4 + F4 )).
Let m be the number of natural guards used in F. From Lemma 8, P( Hn ), a Helix with n − 1
0
0
0
vertices, can be defined by FP = g1 .( g2 + g3 .F4c ) which contains m − 1 guards. By induction
hypothesis, P( Hn ) cannot be defined by fewer than (n − 1) − 2 natural guards. So m − 1
cannot be less than n − 3 and hence m cannot be fewer than n − 2.
Theorem 2. Hn requires exactly n − 2 natural vertex guards.
Proof. From Lemma 1 and Theorem 9, it is obviously implied that Hn requires exactly
n − 2 natural vertex guards.
As we proved, there is an n-gon which needs exactly n − 2 natural vertex guards to be
defined. This implies that n − 2 is the lower bound.
4. Conclusions
Eppstein et al. [3] in 2007 conjectured that for a given number n, at least one simple
polygon is present that requires n − 2 vertex guards to describe the polygon. This is
the worst case of the sculptural garden problem which can be applied to speed up the

Appl. Sci. 2023, 13, 2597

15 of 16

localization approaches of mobile devices in some applications. We proved a special case
of the conjecture in which the guards are natural vertex ones, by introducing a new class
of polygons named Helix polygon. In further research, one can prove the general case of
the conjecture. Additionally, one can investigate the bounds for special cases of polygons
(e.g., orthogonal polygons).
As far as the authors know, no algorithm (deterministic or non-deterministic) has been
presented to solve the sculpture garden problem. It can have many applications in security,
smart cities and the Internet of Things, and it is suggested that researchers try to develop
approximate or heuristic algorithms to solve the problem. To be more precise, it is expected
that in the future research, an algorithm will be presented to solve the problem, in which a
polygon can be described and its range defined with the least number of guards.
Author Contributions: Conceptualization and supervision, M.E.; methodology and validation, M.E.
and B.S.B.; validation and writing—original draft preparation, B.S.B. and M.Z.-S.; resources, M.Z.-S.;
writing—review and editing, B.S.B. All authors have read and agreed to the published version of
the manuscript.
Funding: This research was funded by all the authors equally.
Institutional Review Board Statement: Not applicable.
Informed Consent Statement: Not applicable.
Data Availability Statement: No new data were created or analyzed in this study. Data sharing is
not applicable to this paper.
Conflicts of Interest: The authors declare no conflict of interest.

References
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.

De Berg, M.; Van Kreveld, M.; Overmars, M.; Schwarzkopf, O.C. Computational Geometry; Springer: Berlin/Heidelberg, Germany, 2000.
Eppstein, D.; Goodrich, M.T.; Sitchinava, N. Guard placement for efficient point-in-polygon proofs. In Proceedings of the TwentyThird Annual Symposium on Computational Geometry; ACM: Gyeongju, Republic of Korea, 2007; pp. 27–36.
Eppstein, D.; Goodrich, M.T.; Sitchinava, N. Guard placement for wireless localization. arXiv 2006, arXiv:cs/0603057.
Christ, T.; Hoffmann, M.; Okamoto, Y. Natural wireless localization is NP-hard. In Abstracts 25th European Workshop Computational
Geometry; Citeseer: Brussels, Belgium, 2009; pp. 175–178.
Christ, T.; Hoffmann, M. Wireless Localization with Vertex Guards is NP-hard. In CCCG; Citeseer: Vancouver, BC, Canada, 2009;
pp. 149–152.
Dobkin, D.; Guibas, L.; Hershberger, J.; Snoeyink, J. An Efficient Algorithm for Finding the CSG Representation of a Simple Polygon;
ACM: Atlanta, GA, USA, 1988; Volume 22, Number 4.
Füredi, Z.; Kleitman, D.J. The prison yard problem. Combinatorica 1994, 14, 287–300. [CrossRef]
Estivill-Castro, V.; O’Rourke, J.; Urrutia, J.; Xu, D. Illumination of polygons with vertex lights. Inf. Process. Lett. 1995, 56, 9–13.
[CrossRef]
Steiger, W.; Streinu, I. Illumination by floodlights. Comput. Geom. 1998, 10, 57–70. [CrossRef]
Aichholzer, O.; Fabila-Monroy, R.; Flores-Penaloza, D.; Hackl, T.; Urrutia, J.; Vogtenhuber, B. Modem illumination of monotone
polygons. Comput. Geom. 2018, 68, 101–118. [CrossRef]
Ballinger, B.; Benbernou, N.; Bose, P.; Damian, M.; Demaine, E.D.; Dujmović, V.; Flatland, R.; Hurtado, F.; Iacono, J.; Lubiw, A.
Coverage with k-transmitters in the presence of obstacles. J. Comb. Optim. 2013, 25, 208–233. [CrossRef]
Crepaldi, B.E.; de Rezende, P.J.; de Souza, C.C. An Efficient Exact Algorithm for the Natural Wireless Localization Problem. In
CCCG; Carleton University: Waterloo, ON, Canada, 2013.
Crepaldi, B.E.; de Rezende, P.J.; de Souza, C.C. Solving the natural wireless localization problem to optimality efficiently. Comput.
Geom. 2015, 48, 370–379. [CrossRef]
Cano, J.; Tóth, C.D.; Urrutia, J. A tight bound for point guards in piecewise convex art galleries. Comput. Geom. 2013, 46, 945–958.
[CrossRef]
Karavelas, M.I.; Tóth, C.D.; Tsigaridas, E.P. Guarding curvilinear art galleries with vertex or point guards. Comput. Geom. 2009,
42, 522–535. [CrossRef]
Karavelas, M.I. Guarding curvilinear art galleries with edge or mobile guards via 2-dominance of triangulation graphs. Comput.
Geom. 2011, 44, 20–51. [CrossRef]
Damian, M.; Flatland, R.; O’Rourke, J.; Ramaswami, S. A new lower bound on guard placement for wireless localization. arXiv
2007, arXiv:0709.3554.

Appl. Sci. 2023, 13, 2597

18.
19.

16 of 16

Christ, T.; Hoffmann, M.; Okamoto, Y.; Uno, T. Improved bounds for wireless localization. In Algorithm Theory-SWAT; Springer:
Berlin/Heidelberg, Germany, 2008; pp. 77–89.
Eskandari, M.; Mohades, A.; Bigham, B.S.B. On the Number of Guards in sculpture garden problem. World Appl. Sci. J. 2010, 10,
1255–1263.

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual
author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to
people or property resulting from any ideas, methods, instructions or products referred to in the content.