5th Iranian Conference on

Computational Geometry(ICCG 2022)

Proceedings

Sharif University of Technology
Tehran, Iran, February 24, 2022

Compilation copyright r2022 Mohammad Ali Abam, Hamid Zarrabi Zadeh
Copyright of individual contributions remains with the authors

Foreword
We are pleased to bring you this collection of the accepted papers from the fifth Iranian Conference on Computational
Geometry (ICCG 2022), held at Sharif University of Technology, Tehran, Iran, on February 24, 2022. As ICCG does nothave formal proceedings, the papers presented here could also be submitted to peer-reviewed conferences and journals.
ICCG intends to bring together students and researchers from academia and industry to promote research in the fieldsof Combinatorial and Computational Geometry. All submissions to ICCG 2022 were carefully reviewed by the membersof an international Program Committee comprising 19 leading scientists, and at least three review reports were provided foreach paper. Besides paper presentations, the program included one invited talk by Dr. Prosenjit Bose, a renowned computerscientist from Carleton University, Canada, who gave a presentation in the memory of Dr. Saeed Mehrabi. Due to the
COVID-19 pandemic, ICCG 2022 was forced to run virtually through the excellent facilities provided by Sharif University.
of Technology.
We would like to thank the authors and the invited speaker who contributed to the success of ICCG 2022. We are also
grateful to all PC members for their professional work in providing expert review reports. Last but not least, our gratitude
extends to Sharif University of Technology for generously supporting the conference.
Shahin Kamali and Alireza Zarei (Program Committee Chairs)

Invited Speaker
Prosenjit Bose

Carleton University, Canada

General Chair
Shahin Kamali
Alireza Zarei

University of Manitoba
Sharif University of Technology

Program Committee
Mohammad Ali Abam
Sharareh Alipour
Alireza Bagheri
Yeganeh Bahoo
Sergey Bereg
Ahmad Biniaz
Mansoor Davoodi Monfared
Amin Gheibi
Ali Gholami Rudi
Mahdieh Hasheminezhad
Akitoshi Kawamura
Philipp Kindermann
Jayson Lynch
Debajyoti Mondal
Mostafa Nouri Baygi
Zahed Rahmati
Hamid Zarrabi-Zadeh

Sharif University of Technology
IPM
Amirkabir University of Technology
Ryerson University
University of Texas at Dallas
University of Windsor
Institute for Advanced Studies in Basic
Amirkabir University of Technology
Babol Noshirvani University of Technology
Yazd University
Kyoto University
Universität Würzburg
University of Waterloo
University of Saskatchewan
Ferdowsi University Of Mashhad
Amirkabir University of Technology
Sharif University of Technology

Local Organizers
Mohammad Reza Bahrami
Mohammad Sadegh Borouny

Sharif University of Technology
Sharif University of TechnologyviConference Program
Thursday February 24
Session 1
1

Geometric Spanner in MPC Model
Mohammad Ali Abam, Mohammad Reza Bahrami and Peyman Jabbarzade Ganje

7

Red Blue Set Cover Problem on Axis-Parallel Hyperplanes and Other Objects
Abidha V P and Pradeesha Ashok

11

Angle-Monotonicity of Theta-Graphs for Points in Convex Position
Davood Bakhshesh and Mohammad Farshi

Session 2
19

Guarding Weakly-Visible Polygons with Half-Guards
Hannah Miller Hillberg, Erik Krohn and Alex Pahlow

27

A Randomized Algorithm for Non-crossing Matching of Online Points
Shahin Kamali, Pooya Nikbakht and Arezoo Sajadpour

35

Online Square Packing With Rotation
Shahin Kamali and Pooya Nikbakht

41

Processing Imprecise Points for Diameter Queries
Vahideh Keikha, Sepehr Moradi and Ali Mohadesvii

Invited Talk
45

The final problem I worked on with Saeed Mehrabi.
Prosenjit Bose

Index of Authorsviii

ICCG 2022, Sharif UT, February 24, 2022

Geometric Spanner in MPC Model
Mohammad Ali Abam∗

Mohammad Reza Bahrami†

Abstract

to keeping the dilation as low as possible. Assuming
Erdös girth conjecture, there is a tight bound for generalgraphs that there is a (2k−1)−spanner with O(n1+1/k )edges [19].
The extensiveness of spanners’ applications like approximating shortest path queries, routing distributedand parallel algorithms, designing work efficient PRAM
algorithms [13], and etc. make researchers come up withmany ideas and variants to build them efficiently.

The importance of processing large-scale data is growing rapidly in contemporary computation. In order todesign and analyze practical distributed algorithms, recently, the MPC model has been introduced as a theoretical framework. In this paper, we present the geometric spanner construction in the Massively Parallel
Computing (MPC) model. Constructing θ-graph using
the given ϵ, we modified distributed range tree to findthe nearest point to the apex of a θ-cone efficiently andeform a (1 + ϵ)-spanner in O(1) rounds and O(S)time,where S is the memory size of a single machine.
1

1.2

MPC Model and Geometric Problems

The importance of processing large scale data-set is becoming more crucial every day. Over past years we have
faced exponential growth in the speed of generating new
data. Recently, many tools have been developed to process these data practically, among them Map-Reduce
model [10], Hadoop [21], Spark [22] and Dryad [16]. Dueto the diversity of tools and methods, some general theoretical models were built to conceptualise current andforthcoming tools. One of the most realistic and practical abstract models is Massively Parallel Computing or
MPC for short, which was introduced by Karloff et. al[17], as a computation model for Map-Reduce.
In this model [7], [14], [17], it is assumed that there
are M machines, each of which has a memory of size
S known as local memory and the given input size is
N which distributed arbitrarily. Usually, we assume
the memory size is polynomially smaller than the ine α ) where 0 < α < 1. As theput size, i.e. S = O(Nwhole data must fit into machines, we consider M ≥ N
S.
Also, it is common to add polylog factor to the number
e N ) = O(N/S poly(log N )).
of machines, i.e. M = O(S
Also, despite K-machine model [18], there is no point toepoint connection between machines, so there is a O(S)communication limit for each machine.
However, while we consider graph problems, given agraph G = (V, E) the total memory N is consideredas the number of graph edges E which can be O(n2 )where n = |V |. But we are interested in settings where
local memory is small. Thus, there are three studied
regimes in the MPC model for graph problems; Strongsuperlinear where S ≥ n1+c for a constant c > 0, neare
linear where S = O(n),and strongly sublinear whereγ
S = n for a constant γ < 1.
In geometric problems, especially in geometricgraphs, as the weight function is defined implicitly without keeping all edge weights on memory, we only con-Introduction

We consider the problem of finding a geometric spanner
for a set of points in Rd in the MPC model. In thissection we talk about both the spanner and MPC modeland also we motivate our work. Then the sketch of theproof is presented.
1.1

Peyman Jabbarzade Ganje‡

Spanners

Given an edge-weighted graph G = (V, E), the tspanner of G is a weighted graph S = (V, E ′ ) whereE ′ ⊆ E and for every two vertices u and v, dS (u, v) ≤t · dG (u, v), where dS (u, v) indicates the shortest pathdistance between u and v in graph S. That is, the spanner of graph G, is a graph which preserve the distancesby a t multiplicative factor. For a fixed graph G, thesmallest t, which preserve spanner property is called dilation or stretch factor.
Among general graphs, we are focused on Euclidean
geometric graphs, which are complete graphs with a Euclidean metric edge weight function. Hence, a geometricspanner is a complete Euclidean graph, in which for any
two points we have the weight of edge (u, v) ≤ |uv|,
where |uv| indicates the Euclidean distance between
points u and v.
Also, we can view a spanner as compression for themain graph. Assuredly, the fewest edges it has, the morecompressed it is considered. However, we look forward∗ Department of Computer Science, Sharif University of Technology, Tehran, Iran abam@sharif.edu† Department of Computer Science, Sharif University of Technology, Tehran, Iran mrbahrami@ce.sharif.edu‡ Department of Computer Science, University of Maryland,College Park, MD, US peymanj@cs.umd.edu

15th Iranian Conference on Computational Geometry

sider in the later regime. Henceforth, from now on wee 1−γ ) machines whereconsider n points and M = O(nγeeach of them has S = O(n ) local memory for a constant γ < 1.
1.3

the angle of any two rays emanating at the cone’s apex
and being inside the cone is at most θ. Hence we define
the canonical cone set C, as a collection of O(1/θd−1 )interior disjoint θ-cones, where share apex at the origin.
For a p ∈ Rd , translating each σ ∈ C to the point p,
constructs our θ-graph. Choosing one of the edges ofeach σ ∈ C as representative edge (ℓθ ) the following
lemma from [1] can be stated:

Prior Works

There is an extensive line of research on spanners andalso geometric spanners, especially after Chew [9] introduced them in 1986 but term spanner coined by Pelegand Ullman [20]. In addition to some surveys [11], [15],there is a book completely about geometric spanner [19].
Although there is a classic greedy algorithm for computing geometric spanner [4], there are many works to
reduce the running time while preserving useful properties like minimizing maximum degree or not using too
many more edges. E.g. using θ-graph [5] a geometricspanner can be built in O(n log nd−1 ) time with O(n)edges.
Assuming a large data set, there are some works
on streaming mode like [6], which construct a spanning tree in a single path with O(min(m, kn1+1/k ))edges. Also there is a recent work for general graphby Ghaffari et.al [8], constructs a O(k 1+o(1) )-spannerin O(log log n) rounds in strongly sublinear regime with
O(n1+1/k ·log k) many edges. Also Ghodsi et al. provide
a constant round algorithm in MapReduce framework
to build the geometric spanner in L1 metric in R2 usingO(n/ϵ2 ) edges [3].
In recent years, also, there is a growing line of research to solve the geometric problems in the distributedmodel; such as triangulation algorithms in 2D and 3D[23], or finding the nearest neighbor in K-Machine mode
[12].
1.4

Lemma 1 Let C be a collection of θ-cones, wherecos 2θ − sin 2θ ≥ 1/(1 + ϵ). Choosing ℓσ as representative edge for each θ-cone σ and connecting each point
p to q ∈ σ(p) that its projection on ℓσ minimize theEuclidean distant to p lead us to a (1 + ϵ)-spanner.
Distributed Range Tree A d-dimensional range
tree is a data structure that can answer orthogonal
range queries in O(logd−1 n) time. If d = 1, the range
tree is a balanced binary search tree. For d > 1, therange tree consists of a primary structure in which every node has a range tree on d − 1 dimension for the
point below that node.
Agarwal et al. in [2] show that it is possible to builda range tree in the MPC model efficiently. As the range
tree should be stored in a distributed fashion, a primary
top tree is built which contains O(s1/5 ) top nodes of
the range tree. Hence for each node, the top of the secondary structure build locally and recursively. The procedure continues by using leaves of the primary structure and build the tree recursively. We will use thisstructure and the result of the following theorem from
[2]:
Theorem 2 Given a set P ⊂ Rn , a range tree on P canbe built with size O(n logd−1 n) in constant rounds andO(s logd s) time which can answer orthogonal queries inO(1) rounds and O(logd−1 n) time in MPC model.

Overview of Method

Our algorithm works as follows, for each cone σ we build
a distributed data structure (Next Tree) to obtain thenearest point inside the cone. Inside each cone, it takes
O(d) rounds to find the point which is the nearest one
with respect to its projection on the representative edge.
This is constant if we naturally assume d is constant. To
obtain constant round complexity for all points, we must
re-distribute sub-trees stored on each machine among
searching round, while we look for the nearest point
image on the representative edge. This leads to an algorithm with constant rounds of computation and O(S)
time.
2

3

Next TreeFirst, we consider the definition of Next Tree. The Next
Tree is an augmented distributed range tree that helps
to find the nearest point in a cone to the apex of thequery cone. To build this we amend the range tree [2].
As we discussed earlier, we need a range tree to findthe subset of points inside the query cone σ. Also, weneed to find the nearest point q ∈ σ(p) to connect it to
p in terms of q’s projection to one of σ(p) representative edges or even any arbitrary line at that half-space.
Consider a line in one of the mentioned half-spaces asℓσ , We assume that qσ′ the projection of q on ℓσ is stored
within q.
To build the Next Tree, we add one dimension to eachpoint which contains its rank on ℓσ . This rank can becomputed easily with a constant round of computation[14]. Afterward, a (d + 1)-dimension distributed range
tree is built open this augmented point set Pσ , just like

Preliminaries

θ-graph We use an approach based on θ-graph [1] tobuild our spanner. Given constant ϵ, we choose θ suchthat cos 2θ − sin 2θ ≥ 1/(1 + ϵ). On the other hand,a θ-cone is the intersection of d half-spaces such that2

ICCG 2022, Sharif UT, February 24, 2022

the one appeared in [2]. We only alter the query procedure to find the lowest rank point in the canonicalsubset. This leads us to the following lemma:

Now we must show how find nearest works in parallel for all points. If we want to find the nearest point
one by one it takes O(n) rounds to build the spanner
which is unacceptable in our model.
By lemma 4, it is clear that query one point in the
Next Tree requires O(1) rounds of computation. However, we design an algorithm to find the next point, theadjacent vertex in the desired spanner, for all points inconstant rounds. To this end, we must be able to initiate the search procedure locally for all machines. Hence,each machine needs to have the top sub-tree or the master node which contains the top O(S 1/5 ) nodes [2]. Thiscan be done on logS 1/5 n = O(1) rounds of computation
using the broadcast tree [14]. Afterward, in each machine Mi , s points have been searched and in the next
step their search procedure must continue among set
Mi = {M1 , . . . , Ms }. As a result, we can imagine somecases in which a machine is overwhelmed by Ω(S) nodes
to resume its search procedure. To resolve this problem,at the end of the first searching round, each machine
sends the number of applicant nodes to their destination machine say Mi . As each machine sends a number
to Mi , if the sum of these numbers exceeds S, Mi shouldmake a copy of its self and inform nodes about the newdestinations. Mi choose these machines randomly. Also
it sends the number of required machines, so using thebroadcast tree, we can handle the distribution. The following lemma shows us that this procedure (algorithm2) can be done on constant rounds of computation.

Lemma 3 For a point set P ⊂ Rd , Next Tree can bebuilt in O(d) rounds, in O(s logd+1 n) time with sizeO(n logd n).
A query to Next tree is an orthogonal cone σ(p). The
desired response is a point q where qσ′ , the projection ofq on ℓσ , is the next projected point on ℓσ and q ∈ σ(p).
Lemma 4 In d-dimension Next Tree, the next query
can be answered in O(1) rounds and O(logd+1 n) time.
Proof. Without loss of generality consider a orthogonalcone σ(p) = (x1 , . . . , xd ) which is open to (+∞, +∞).
Just like distributed range tree for each query, we mustgo through the data structure. For each xi , where i ≤ d,our search in Next Tree is a path with at most O(log n)points. Just like lemma 3, we must repeat it for each dlevel. However, at the d+1 level, we take a O(log n) pathjust to find the minimum ranked point as the (d + 1)thcoordinate of q is rank of qσ , which takes O(1) roundand O(logd+1 n) time for a single point.
□
4

Spanner Construction

Briefly, the procedure of constructing the spanner is asfollows, as algorithm 1 specify, for each canonical cone
σ, we transform points and build a Next Tree. Then wefind the nearest point to each cone’s apex and connectthem.

Lemma 6 Targeted sub-trees to resume the query procedure to find neighbour of the point subject to a cone σ
can be redistributed to be able to host all requests at around, with O(1) rounds of computation and O(S) time.

Algorithm 1 Distributed algorithm to build a (1 +ϵ) − spanner using θ-graph
Require: Point set P , ϵ, n nodes distributed arbitrary
1: Compute θ based on ϵ and canonical θ - cones C
2: for all σ in C do
3:transform and order points(σ, ℓσ )4:
Tσ = build next tree(σ)
5:find nearest(P , Tσ )6: end for

Proof. Notice that, the total number of points is n andalso a machine requires another helping machine for every O(S) applicant point. As S ≥ s = n/M , where s isthe number of points hosted by each machine, the total number of sub-trees to redistribute is less than M .
This is also an upper bound for redistributing a fixed
sub-tree. Again using the broadcast tree to distributethe sub-trees. A machine with exceeded query requests
should choose uniformly at random max (S, r/S) machines, where r is the number of arriving requests. Using the broadcast tree this will end up in the constantround. However, if a machine receives more nodes thanits memory size, it should drop extra sub-trees. So, we
consider Xi the number of guest sub-trees requested tojoin Mi . As E[Xi ] = 1 we can use chernoff bound:

Recall that for each 1 ≤ i ≤ n, σ(pi ) is translated of
the same canonical cone σ ∈ C. Henceforth, we need toproject all points into ℓσ and also transform all points toform all σ(pi ) orthogonal. After that, we must computethe rank of each projected point on ℓσ which can bedone in a constant rounds for all points [14]. Hence thefollowing proposition is inferred:
Proposition 5 In algorithm 1, the procedure transform and order points project the points onto ℓσ anderank them in O(1) rounds and O(S)time.

P r[Xi ≥ log n] ≤ exp(

1
− log2 n)≤ 2
3n

Using union bound, the probability of no machine re3

5th Iranian Conference on Computational Geometry

ceive more than O(log n) nodes is:
P r[X1 ∪ · · · ∪ XM ] ≤

M
X
1
1

n2

=

Algorithm 2 find nearest(P, Tσ )Require: Point set P and its projection on ℓσ within,
Pre-computed and stored Tσ , Constant k =logS 1/5 n = O(1)1: Distribute the master node to all machines and set
as current searching node Mi on each machine
2: for k times do
3:
Perform the search on Mi locally and find theMi machine set to resume the search
4:
Inform Mi members about the coming requests
5:
Redistribute the machine Mi if necessary
6: end for
Using proposition 5 and lemma 3, we conclude thatthe first two lines of the for loop in Algorithm 2 requireseO(1) rounds and O(S)time. Moreover, by lemmas 4
and 6 the find nearest procedure requires O(1) rounds
and O(S) time. Assuming d and ϵ are constants leads
to the following theorem:
Theorem 7 In the MPC model, a geometric (1 + ϵ)spanner can be built using O(1) rounds of computationeand O(S)
time.

[3]

S. Aghamolaei, F. Baharifard, and M. Ghodsi,“Geometric spanners in the MapReduce model,”in Lecture Notes in Computer Science, Springer
International Publishing, 2018, pp. 675–687.

[4]

I. Althöfer, G. Das, D. Dobkin, D. Joseph, and J.
Soares, “On sparse spanners of weighted graphs,”
Discrete Comput. Geom., vol. 9, no. 1, pp. 81–100,
Dec. 1993.

[5]

S. Arya, D. M. Mount, and M. Smid, “Dynamic
algorithms for geometric spanners of small diameter: Randomized solutions,” Computational Geometry, vol. 13, no. 2, pp. 91–107, 1999.

[6]

S. Baswana, “Streaming algorithm for graphspanners—single pass and constant processing
time per edge,” Information Processing Letters,
vol. 106, no. 3, pp. 110–114, 2008.

[7]

P. Beame, P. Koutris, and D. Suciu, “Communication steps for parallel query processing,” inProceedings of the 32nd ACM SIGMOD-SIGACTSIGAI Symposium on Principles of Database Systems, ser. PODS ’13, New York, New York,
USA: Association for Computing Machinery,
2013, pp. 273–284.

[8]

A. S. Biswas, M. Dory, M. Ghaffari, S. Mitrović,and Y. Nazari, “Massively parallel algorithms for
distance approximation and spanners,” in Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures, ser. SPAA
’21, Virtual Event, USA: Association for Computing Machinery, 2021, pp. 118–128.

[9]

L. Chew, Paul, “There are planar graphs almost
as good as the complete graph,” Journal of Computer and System Sciences, vol. 39, no. 2, pp. 205–
219, 1989.

[10]

J. Dean and S. Ghemawat, “Mapreduce: Simplified data processing on large clusters,” Commun.
ACM, vol. 51, no. 1, pp. 107–113, Jan. 2008.

[11]

D. Eppstein, “Chapter 9-spanning trees and spanners,” Handbook of Computational Geometry,pp. 425–461,

Concluding Remarks

We considered constructing a geometric spanner in the
MPC model. Benefiting from θ-graph, we designed analgorithm to build this spanner in constant rounds ofcomputation. However, we can consider the same problem to find a spanner with a smaller final degree. Also,
we can consider the problem in dynamic or kinetic models if we consider the possibility of temporal changes inour point, with less work.
References[1]

P. K. Agarwal, K. Fox, K. Munagala, and A. Nath,“Parallel algorithms for constructing range andnearest-neighbor searching data structures,” inProceedings of the 35th ACM SIGMOD-SIGACTSIGAI Symposium on Principles of Database Systems, ser. PODS ’16, San Francisco, California, USA: Association for Computing Machinery,
2016, pp. 429–440.

M
1
≤
n2
n

So, with high probability, no machine receives moree δ ), thethan log n nodes. Using the fact that S = O(nlemma concludes.
□

5

[2]

M. A. Abam and M. de Berg, “Kinetic spanners in Rd ,” in Proceedings of the Twenty-Fifth
Annual Symposium on Computational Geometry,ser. SCG ’09, Aarhus, Denmark: Association for
Computing Machinery, 2009, pp. 43–50.

4

ICCG 2022, Sharif UT, February 24, 2022

[12]

R. Fathi, A. R. Molla, and G. Pandurangan, “Efficient distributed algorithms for the k-nearest
neighbors problem,” in Proceedings of the 32nd
ACM Symposium on Parallelism in Algorithms
and Architectures, ser. SPAA ’20, Virtual Event,
USA: Association for Computing Machinery,
2020, pp. 527–529.

[13]

S. Friedrichs and C. Lenzen, “Parallel metric treeembedding based on an algebraic view on moorebellman-ford,” J. ACM, vol. 65, no. 6, Nov. 2018.

[14]

M. T. Goodrich, N. Sitchinava, and Q. Zhang,“Sorting, searching, and simulation in the mapreduce framework,” in Proceedings of the 22ndInternational Conference on Algorithms andComputation, ser. ISAAC’11, Yokohama, Japan:
Springer-Verlag, 2011, pp. 374–383.

[15]

J. Gudmundsson and C. Knauer, “Dilation anddetours in geometric networks,” Handbook of Approximation Algorithms and Metaheuristics Chapman & Hall/CRC Computer & Information Science Series, 2007.

[16]

M. Isard, M. Budiu, Y. Yu, A. Birrell, and D. Fetterly, “Dryad: Distributed data-parallel programsfrom sequential building blocks,” SIGOPS Oper.
Syst. Rev., vol. 41, no. 3, pp. 59–72, Mar. 2007.

[17]

H. Karloff, S. Suri, and S. Vassilvitskii, “A modelof computation for mapreduce,” in Proceedings of
the Twenty-First Annual ACM-SIAM Symposium
on Discrete Algorithms, ser. SODA ’10, Austin,
Texas: Society for Industrial and Applied Mathematics, 2010, pp. 938–948.

[18]

H. Klauck, D. Nanongkai, G. Pandurangan, and
P. Robinson, “Distributed computation of largescale graph problems,” in Proceedings of theTwenty-Sixth Annual ACM-SIAM Symposium on
Discrete Algorithms, ser. SODA ’15, San Diego,
California: Society for Industrial and Applied
Mathematics, 2015, pp. 391–410.

[19]

G. Narasimhan and M. Smid, Geometric Spanner Networks. USA: Cambridge University Press,
2007.

[20]

D. Peleg and J. D. Ullman, “An optimal synchronizer for the hypercube,” in Proceedings of thesixth annual ACM Symposium on Principles of
distributed computing, 1987, pp. 77–85.

[21]

T. White, Hadoop: The definitive guide. ” O’Reilly
Media, Inc.”, 2012.

[22]

M. Zaharia, M. Chowdhury, M. J. Franklin, S.
Shenker, and I. Stoica, “Spark: Cluster computing with working sets,” in Proceedings ofthe 2nd USENIX Conference on Hot Topics inCloud Computing, ser. HotCloud’10, Boston, MA:
USENIX Association, 2010, p. 10.

[23]

5

H. Zhou, H. Wu, S. Xia, M. Jin, and N. Ding,“A distributed triangulation algorithm for wireless sensor networks on 2d and 3d surface,” in 2011
Proceedings IEEE INFOCOM, 2011, pp. 1053–
1061.

6

ICCG 2022, Sharif UT, February 24, 2022

Red Blue Set Cover Problem on Axis-Parallel Hyperplanes and Other
Objects
Abidha V P∗

Pradeesha Ashok

Abstract

hyperplanes under an array of parameters and all possible combinations of those parameters.

In this paper we study the Red Blue Set Cover problem which is a bichromatic variant of the set cover problem. We prove that the Red Blue Set Cover problem is NP-hard even for red and blue points in IR2 andset of axis parallel lines. We then study the parameterized complexity of a generalization of this problem, forpoints in IRd and a family of axis-parallel hyperplanesin IRd , under different parameterizations. We further
consider the Red Blue Set Cover problem for somespecial types of rectangles in IR2 .
1

1.1

Problems studied and results

We study the decision variant of a geometric version of
the RBSC problem where given R∪B, and F ⊆ 2U andkr ∈ N, our objective is to decide if there exists F 0 ⊆ Fthat covers all points in B and at most kr points fromR.
Theorem 1 (*) The RBSC problem on axisparallel lines is NP-complete.1

Introduction

The Set Cover problem and its variants are well studied in Computer Science [2]. Given a universe U with nelements and a family F of subsets of U, the minimum
Set Cover problem is to find a subset F 0 ⊆ F thatcovers all elements in U and |F 0 | is minimized. Hereu ∈ U is said to be covered by F 0 , if ∃F ∈ F 0 such thatu ∈ F.
In this paper, we study a generalization of the Set
Cover problem, where U is bi-chromatic. Given a universe U = R ∪ B of a finite set R of red elements, and afinite set B of blue elements and a family F of subsetsof U, the Red Blue Set Cover (RBSC) problem is
to find a subset F 0 of F that covers all blue points of B
and the minimum number of red points from R. Here,R and B are points in IRd . The sets in F correspond to
maximal subset of points contained in geometric objectsof a certain type. Note that the number of sets in F 0 is
not optimized. The minimum Set Cover problem canbe considered as a special case of the RBSC problem
where every set contains a distinct red element.
The RBSC problem was introduced by Carr et al. [3]in 2000, motivated by applications in data mining. Geometric variants of the RBSC problem are also studied. Approximation algorithms for different geometric
RBSC problems are given in [4, 8].
The geometric RBSC problem is also studied in thecontext of Parameterized complexity. Ashok et al.[1] investigate parameterized algorithms on general lines andWe study the following variants of the RBSC problem.

∗ International Institute of Information Technology Bangalore,
India. abidha.vp@iiitb.ac.in, pradeesha@iiitb.ac.in

1 The proofs of the results marked with a star are in the fullversion of the paper.

AxRBSC-hyperplane: We study the RBSC problem
for a generalization of lines to d dimension. We consider
the problem where U is a set of points in Rd and F isdefined by a set of axis-parallel hyperplanes. This problem is NP-hard by theorem 1. We study the parameterized complexity of AxRBSC-hyperplane under different parameterizations. For each parameter, we consider whether the problem is fixed parameter tractable
and if yes, we investigate whether the problem admits
polynomial kernels. We show that the RBSC problem
admits more positive results when restricted to axisparallel hyperplanes as compared to hyperplanes of any
orientation.
AxRBSC-skylines: Bi-directional strips are either ofthe form [a, b] × (−∞, ∞) or (−∞, ∞) × [a, b]. Notethat axis-parallel lines is a special case of bi-directional
strips and hence the RBSC problem on bi-directional
strips is NP-Hard. We study the RBSC problem onskylines which are rectangles of the form [a, b] × (−∞, c]or (−∞, c] × [a, b] (referred to as AxRBSC-skylines)
and show that this problem is W[1]-hard and therefore
unlikely to admit FPT algorithms.
AxRBSC-quadrants: We further consider quadrants,
a special case of skylines. Quadrants are axis-parallel
rectangles of the form [a, b] × (+∞, +∞). We show that
the RBSC on quadrants is polynomial time solvable.

75th Iranian Conference on Computational Geometry

1.2

Preliminaries

contains sets corresponding to every blue point, wherea set corresponding to a blue point b contains all thered points contained in the at most d hyperplanes that
contain b. It is easy to see that (R ∪ B, H, kr ) is a YES
instance if and only if (U, F, k) is a YES instance.
Our branching algorithm considers a blue point b suchthat at least one hyperplane that contains b has two
red points and branches on the hyperplane that covers
b in the solution. Thus, kr drops by at least 2 in atleast one branch and drops by at least one in all otherbranches. This gives us a branching algorithm
that runs√

In this paper, we study the parameterized complexityof the problems using different parameters. Here weO(1)aim to solve the problems in f (k) · |n|time, forsome computable function f and k << n. For detailed
reading of parameterized complexity, refer to [5].
Notations: Let P = R ∪ B be a point set, where R isa set of r red points and B is a set of b blue points and|R| + |B| = n. For any point p, let x(p) and y(p) denote
the x and y coordinate values of p respectively. Let [d]be the set, {1, 2, · · · , d}.
We use the following reduction rules exhaustively on
any instance of the RBSC problem in multiple sections
throughout the paper.

d−1+Reduction rule 1 If a blue point b is contained inonly one set S ∈ F, then delete S from F, S ∩ B from
B and S ∩ R from R, set kr = kr − |S ∩ R|.
Reduction rule 2 If a set S contains only red points,
then delete S.
Reduction rule 3 If a set S contains only blue points,
then delete S from F and S ∩ B from B.
Reduction rule 4 If a set S contains more than kr
red points, then delete S from F.
2(d−1)2 +4. If thein O(cd kr .nO(1) ) time where cd =2
instance does not contain such a blue point, then thealgorithm converts this to a d-Hitting Set instance.
d-Hitting Set admits a branching algorithm that runsin O(cd k .nO(1) ) time [7].
Corollary 3 The RBSC problem on AxRBSChyperplane in IRd is FPT parameterized by kr + d.
Polynomial Kernels: We apply the following set of
reduction rules for all j = 1 to d − 1 exhaustively. For
2 ≤ j ≤ d−1, we apply the reduction rule corresponding
to j only when reduction rule corresponding to (j − 1)
is not applicable. For a point p ∈ Rd , xi (p) denotes thevalue of the ith coordinate of p, for 1 ≤ i ≤ d.

RBSC on Axis-parallel hyperplanes

Reduction rule 5 Repeat for all d0 ⊂ [d] such that|d0 | = d − j.
Let B 0 ⊆ B be such that for all p, q ∈ B 0 , xi (p) = xi (q)if i ∈ d0 . If |B 0 | > j!(kr )j then delete all but j! · krj + 1
points of B 0 .

Parameterizing by kr : In this section, we consider
AxRBSC-hyperplane parameterized by kr . Let (R ∪B, H, kr ) be an instance of AxRBSC-hyperplane parameterized by kr .
After applying reduction rules 1, 2 and 3 on (R ∪B, H, kr ), every hyperplane contains at least one redpoint and at least one blue point. Every blue point iscovered by at most d hyperplanes. There is a branchingalgorithm that can solve this problem in FPT time. For
a blue point, we can branch on the hyperplane thatcovers it in the solution (if it exists). On every branch,
the budget kr drops by at least one, thus giving us analgorithm that runs in O(dkr ) time. The next result
improves this running time.

Lemma 4 (*) Reduction rule 5 is safe.
Theorem 5 AxRBSC-hyperplane admits a kernel(R ∪ B, H) with |B| ≤ d!krd , |R| ≤ d · d! · krd+1 ,|H| ≤ d · d!krd .
Proof. Let (R ∪ B, H, kr ) be an instance of AxRBSChyperplane such that none of the reduction rules areapplicable. Then, if it is a YES instance, all the points in
B can be covered by at most kr .d hyperplanes. Any hy(d−1)
perplane can contain at most (d − 1)!kr
blue points,
otherwise Reduction Rule 5.(d−1) can be applied. Thus
a YES instance can have at most d!krd blue points.
Every hyperplane in H contains at least one blue
point and any blue point is contained in at most d hyperplanes. Therefore, |H| ≤ d.d!krd . By Reduction Rule4, a hyperplane contains at most kr red points. Thus
|R| ≤ d.d!.krd+1 .


Theorem 2 The problem AxRBSC-hyperplane in
kr O(1)
IRd can) where cd =√ be 2solved in time O(cd .nd−1+ (d−1) +4.
2
Proof. Here, we consider different cases. One case iswhen every hyperplane contains exactly one red point.
We observe that this case can be reduced to the dHitting Set problem parameterized by the solution
size. Let (R ∪ B, H, kr ) be an instance of AxRBSChyperplane such that every H ∈ H contains exactly one red point from R. We construct an instance(U, F, k) of d-Hitting Set with U = R, k = kr and F

Parameterizing by b: Since every blue point is contained in at most d hyperplanes, the next result is easy
to see.
8

ICCG 2022, Sharif UT, February 24, 2022

Lemma 6 The AxRBSC-hyperplane problem parameterized by b can be solved in time O(db .nO(1) ).

To bound the number of blue points, we use the following reduction rule. We apply the following set of
reduction rules for all j = 1 to d − 1 exhaustively. For
2 ≤ j ≤ d−1, we apply the reduction rule corresponding
to δ only when reduction rule corresponding to (j − 1)jX
is not applicable. Let Aj =hi .

Theorem 7 The AxRBSC-hyperplane problem parameterized by b admits a polynomial kernel.
Proof. Since, we cannot apply reduction rules anymore
on (R ∪ B, H, kr ), every hyperplane contains at least
one blue point. One blue point is covered by at mostd-hyperplanes. Then the number of hyperplanes H is at
most db. To bound the number of red points we reduce
our AxRBSC-hyperplane instance to a Weighted
AxRBSC-hyperplane instance as follows:
The family of hyperplanes and the set of blue points
remain the same as in the reduced instance. Let Rd ⊂ R
be the set of red points that lie in the intersection of d
hyperplanes in H. For all r ∈ Rd , assign w(r) = 1.
Since any d hyperplanes in Rd intersect at a point,|Rd | ≤ hd . For i = 1 to d − 1, we perform the reduction as follows. For all sets of i hyperplanes in H,
say, Hi = {h1 , h2 , . . . , hi }, consider the set of red points
that is contained in all hyperplanes of Hi and no otherhyperplane in H. In the reduced instance, delete all but
one of these red points and assign a weight equal to thenumber of deleted points +1.
It easy to see that AxRBSC-hyperplane has a solution of size k if and only if WEIGHTED AxRBSChyperplane has a solution of total weight k.
In the reduced instance, the number of red points
that lie in the intersection of exactly i hyperplanes is
O(hi ). Therefore the total number of red points in the
reduced instance is O(hd + hd−1 + hd−2 + · · · + h) =O(hd ) = O((db)d ). Now we bound the weight of eachred point in the reduced instance. By Reduction rule4, all hyperplanes in H contain at most kr red points.
Therefore, the weight of any red point is at most kr . We
see that we need at most h bits to encode the weight ofa red point. If not, kr > 2h . Note that there exists abrute force algorithm that solves the problem in O(2h )time. If 2h < kr , this is a polynomial time algorithm.
Hence it follows that the weight can be encoded usingh ≤ db bits. Hence the size of the reduced instance isO((db)d+1 ).
There exists a polynomial-time many-one reduction
from WeightedAxRBSC-hyperplane to AxRBSChyperplane[1]. Thus, we obtain a polynomial-size kernel for AxRBSC-hyperplane parameterized by b.


i=0

Reduction rule 6 Repeat for all d0 ⊂ [d] such that|d0 | = d − j.
Let B 0 ⊆ B such that for all p, q ∈ B 0 , xi (p) = xi (q) if
i ∈ d0 . If |B 0 | > Aj then delete all but Aj + 1 points of
B0.
Lemma 8 (*) Reduction rule 6 is safe.
Exhaustive application of the reduction rule 6 gives
an equivalent instance of the problem. Now the next
theorem follows.
Theorem 9 (*) The AxRBSC-hyperplane parameterized by h admits a polynomial kernel.
3

Red Blue Set Cover on Skylines

Given P = R ∪ B in the plane and K, a set of m bidirectional skylines, We prove that, AxRBSC-skylines parameterized by kr is W[1]-hard by giving a parameterized reduction from the Square Stabbing problem.
Rectangle Stabbing : Given a set S of n rectangles
and a set of axis-parallel lines L, the Rectangle Stabbing problem is to decide whether there exists a subset
L0 ⊆ L with |L0 | ≤ k such that every rectangle from S isintersected (stabbed) by at least one line in L0 . If all therectangles are unit squares it is the Square Stabbing
problem. Square Stabbing problem parameterized
by k is known to be W[1]-hard [6].
Let (S, L) be an instance of the Square Stabbing
problem. Let {l1 , l2 , ..ln } be the set of vertical lines in L
which are in non-decreasing order of their x-coordinates
and let {h1 , h2 , ..hn } be the set of horizontal lines in L
which are in non-increasing order of their y-coordinates.
For every square S ∈ S, add a blue point bS to P at
the top-left corner of S. For every vertical line li , we
add a unit width vertical skyline Sli with its right edge
coinciding with the given line li . The top edge of theleftmost vertical skyline Sl1 is unit distance above thetopmost point in P . For i > 1, the top edge of theskyline Sli is unit vertical distance away from the topedge of Sli−1 . Similarly for all horizontal lines, we add
a unit width horizontal skyline Shi whose bottom edge
coincides with the line hi . The right edge of the topmost
horizontal skyline Sh1 is a unit distance away from therightmost point in P . The right edge of Shi is unithorizontal distance away from the Shi−1 , for i > 1. For
every horizontal skyline, add a red point to P in the topright corner of the skyline and for every vertical skyline,

Parameterizing by h: We design a parameterized algorithm and a kernel for AxRBSC-hyperplane whenparameterized by the number of hyperplanes, h. We
enumerate all possible subsets of H and for each subset,
we check in polynomial time whether it covers all blue
points and at most kr red points. The algorithm runsin time O(2h (|U | + |F |).
9

5th Iranian Conference on Computational Geometry

add a red point to P in the top-left corner of the skyline.
Thus every skyline has a unique red point.
Lemma 10 (*) < S, L > can be stabbed using k lines
if and only if < P, K > has a solution of size k.
Theorem 11 The RBSC problem on bidirectional skylines is W[1]-hard parameterized by the solution size.
This implies that RBSC problem on axis parallel
rectangles is W[1]-hard parameterized by the solution
size k.
4

Quadrants

In this section, we give a polynomial time algorithm tooptimally solve the AxRBSC-quadrants problem.
Given a universe U = R ∪ B and a family Q1 of quadrants, find the subfamily Q01 that covers all points from
B and minimum possible number of red points from R.
Observation 12 Let qi and qj be two nested quadrantsi.e., (qi ∩ B) ⊆ (qj ∩ B) and (qi ∩ R) ⊆ (qj ∩ R) .
Then both q1 and q2 together are not part of an optimal
solution of AxRBSC-quadrants.
Theorem 13 For a given bichromatic point set withn points, RBSC using quadrants can be computed inO(mn2 ) time.

Let dp[i, j] returns the minimum number of red points
from Ri , that is covered by a subset of Qj that covers all
points in Bi . Then dp[ ] can be given as follows. Hereb0 is the blue point with the smallest σ(b0 ) value in Bi .
dp[i, j] =min0

Q∈Qj ,b ∈Q
dp[bottom(Q), lef t(Q)] + |Q ∩ Ri |}(1)
To see the correctness of the above, observe that therecurrence considers all Q ∈ Qj to cover b0 . For thecorrect guess, the rest of the solution only covers uncovered red points from Rbottom(Q) using Q ∈ Qlef t(Q) .
Otherwise, if a Q ∈/ Qlef t(Q) is part of the solution thenit contradicts Observation 12. Similarly an uncovered
red point outside Rbottom(Q) is not part of an optimal
solution.
It is clear that computing the value of one DP tableentry takes O(m) time. The number of dp[∗, ∗] values
to be computed is clearly O(n2 ) time. We can construct and verify the orthogonal path in O(n log n) time.
Therefore, the algorithm runs in O(mn2 ) time.

References[1] Pradeesha Ashok, Sudeshna Kolay, and Saket Saurabh.
Multivariate complexity analysis of geometric red blue
set cover. Algorithmica, 79(3):667–697, 2017.

Proof. Let O be the orthogonal convexhull of B. Consider the left-bottom chain, Plb , of O i.e., the chain of
O that extends from the blue point with the minimum
x-coordinate to the blue point with the minimum ycoordinate, in the anti-clockwise direction. Let B 0 ={b1 , b2 , · · · bl } be the set of blue points on Plb ordered byincreasing x-coordinate. Note that this is also an orderof decreasing y-coordinate. Let R0 ⊆ R and B 00 ⊆ B \B 0respectively be the set of red and blue points that lie
on the right side of Plb . Any set of quadrants thatcover all points in B 0 will cover all points in B 00 and
R0 . Therefore it is enough to consider the AxRBSCquadrants problem for (R = (R\R0 ) ∪ (B = B 0 ), Q1 ).
For this reduced instance (R ∪ B, Q1 ), we introduce
the following notations. Let π : R ∪ B 7−→ [n] be thebijection corresponding to the ordering of the points in
R ∪ B by increasing x coordinates and σ : R ∪ B 7−→ [n]be the bijection corresponding to the ordering of thepoints in R ∪ B by decreasing y coordinates. For any
Q ∈ Q1 , let p ∈ Q∩(R∪B) be the point with smallest x
coordinate in Q and let q ∈ Q∩(R∪B) be the point withthe smallest y coordinate in Q. Define lef t(Q) = π[p]and bottom(Q) = σ(q). Let Bi = {b ∈ B|σ(b) > i},
Ri = {r ∈ R|σ(r) > i} and Qj = {Q ∈ Q1 |lef t(Q) >j}.
Now we give a dynamic programming algorithm tosolve the AxRBSC-quadrantsproblem for this instance.

[2] Shuai, Tian-Ping and Hu, Xiao-Dong. Connected set
cover problem and its applications. International Conference on Algorithmic Applications in Management,
243–254, 2006.
[3] Robert D Carr, Srinivas Doddi, Goran Konjevod, andMadhav Marathe. On the red-blue set cover problem.
In Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, pages 345–353, 2000.
[4] Timothy M. Chan and Nan Hu. Geometric red-blue set
cover for unit squares and related problems. Computational Geometry, 48:380–385, 2015.
[5] Fomin F.V. Kowalik L. Lokshtanov D. Marx D.
Pilipczuk M. Pilipczuk M. Saurabh S Cygan, M. Parameterized algorithms. In Journal of Algorithms, pages
99–127, 2005.
[6] Michael Dom, Michael R. Fellows, and Frances A. Rosamond. Parameterized complexity of stabbing rectangles
and squares in the plane. WALCOM ’09, pages 298–309,
Berlin, Heidelberg, 2009. Springer-Verlag.
[7] Rolf Niedermeier and Peter Rossmanith. An efficient
fixed-parameter algorithm for 3-hitting set. Journal ofDiscrete Algorithms, 1(1):89–102, 2003. Combinatorial
Algorithms.
[8] S Pandit RR Madireddy, SC Nandy. On the geometricred-blue set cover problem. WALCOM, pages 129–141,
2021.

10

ICCG 2022, Sharif UT, February 24, 2022

Angle-Monotonicity of theta-graphs for points in convex position
Davood Bakhshesh∗

Mohammad Farshi†

Abstract
For a real number 0 < γ < 180◦ , a geometric path
P = (p1 , . . . , pn ) is called angle-monotone with width γ
from p1 to pn if there exists a closed wedge of angle γ−−→
such that every directed edge −p−
i pi+1 of P lies inside thewedge whose apex is pi . A geometric graph G is called
angle-monotone with width γ if for any two vertices pand q in G, there exists an angle-monotone path withwidth γ from p to q. In this paper, we show that for
any integer k ≥ 1 and any i ∈ {2, 3, 4, 5}, the thetagraph Θ4k+i on a set of points in convex position is360◦
angle-monotone with width 90◦ + iθ
4 , where θ = 4k+i .
Moreover, we present two sets of points in the plane, one
in convex position and the other in non-convex position,
to show that for every 0 < γ < 180◦ , the graph Θ4 is
not angle-monotone with width γ.

−−→
for every integer i with 1 ≤ i ≤ n − 1, the vector −p−
i pi+1θlies in the wedge Wpi . Using the concept of θ-paths,
Bonichon et al. [3] introduced angle-monotone graphs.
A geometric graph G = (S, E) is called angle-monotone
if for any two points u, v ∈ S, there is a real number
θ > 0 such that G contains a θ-path between u andv. Bonichon et al. [3] generalized the concept of anglemonotone graphs to angle-monotone graphs with width
γ. Let γ be a real number with 0 < γ < 180◦ . A geometric path P = (p1 , . . . , pn ) is called angle-monotonewith width γ from p1 to pn if for some closed wedge−−→of angle γ, every vector −p−
i pi+1 lies in the wedge whose
apex is pi (see Figure 1).

145◦

1

y

Introduction

Let S be a set of points in the plane. For two points
p, q ∈ S, the Euclidean distance between p and q isdenoted by |pq|. A geometric graph G = (S, E) isa weighted graph such that any edge (x, y) of G is astraight-line segment between x and y and the weight of(x, y) is |xy|. The length of a path P = (p1 , p2 , . . . , pr )between p1 and pr in G is denoted by |P |, and it isPr−1
defined as |P | =i=1 |pi pi+1 |. For any two points
p, q ∈ S, the stretch factor (or dilation) between p andq in a geometric graph G is the ratio of the length ofa shortest path between p and q in G over |pq|. The
stretch factor of a geometric graph G is the maximum
stretch factor between all pairs of vertices of G.
Let t > 1 be a real number. A geometric graph G iscalled a t-spanner if the stretch factor of G is at mostt. In Computational Geometry, constructing the geometric graphs with low stretch factor, small numberof edges (small size) and low weight is an important
problem. We refer the reader to the book [9] to study
t-spanners and their algorithms.
Let θ > 0 be a real number. In [6], Dehkordi et al.,introduced θ-paths. Let Wpθ be a 90◦ closed wedge delimited by the rays starting at p with the slopes θ − 45◦and θ + 45◦ . A path (p1 , p2 , . . . , pn ) is called a θ-path if∗ Department of Computer Science, University of Bojnord, Bojnord, Iran. d.bakhshesh@ub.ac.ir† Department of Mathematical Sciences, Yazd University,
Yazd, Iran. mfarshi@yazd.ac.ir

11

145◦
145◦

x

145◦

Figure 1: An angle-monotone path between x and ywith width γ = 145◦ .
A geometric graph G is called angle-monotone withwidth γ if for any vertex p of G, there is an anglemonotone path with width γ from p to all other verticesof G. It is remarkable that if a path is angle-monotonewith width γ from x to y, then the path is also anglemonotone with width γ from y to x.
In [6], Dehkordi et al. show that any Gabriel triangulation is an angle-monotone graph with width 90◦ . In[8], Lubiw and Mondal show that for any set of points inthe plane, there is an angle-monotone graph with width
90◦ with a subquadratic size. Furthermore, they showedthat for any angle β with 0 < β < 45◦ , and for any
set of points in the plane, there is an angle-monotone
graph with width (90◦ + β) of size O( nβ ). Bakhshesh
and Farshi [1] present a point set in the plane such that

5th Iranian Conference on Computational Geometryits Delaunay triangulation is not angle-monotone withwidth less than 140◦ . Bakhshesh and Farshi [2] provethat the minimum value of an angle γ such that forany set of points in the plane there is a plane anglemonotone graph with width γ is equal to 120◦ .
One of the most popular graphs in computational
geometry are theta-graphs which were introduced by
Clarkson [5] and independently by Keil [7]. Informally,for every point set S in the plane and an integer m ≥ 2,
the theta-graph Θm is constructed by partitioning theplane into m cones at each point p ∈ S, and joining
the closest point to p at each cone (in the next section,
closest will be defined). Bonichon et al. [3] proved thatfor any set of points in the plane, half-Θ6 -graph, a planesubgraph of Θ6 , whose edges are obtained by selecting
every other cone, i.e., alternate cones, is angle-monotonewith width 120◦ . In [6], Dehkordi et al. prove that forevery set of n points in the plane that are in convex
position, there exists an angle-monotone graph (anglemonotone graph with width 90◦ ) with O(n log n) edges.
To the best of our knowledge, it is unknown if the thetagraphs except Θ6 are angle-monotone with a constantwidth.
In this paper, we show that for any set of points
in convex position, and any integer k ≥ 1 and anyi ∈ {2, 3, 4, 5}, the theta-graph Θ4k+i is angle-monotone
360◦
with width 90◦ + iθ
4 , where θ = 4k+i . Moreover, we
present two sets of points in the plane, one in convex
position and the other in non-convex position, to showthat for every 0 < γ < 180◦ , the graph Θ4 is not anglemonotone with width γ.

C1p

C0p
p

p
Cm−1

p
Cm−2

Figure 2: Partition the plane into m = 18 cones withapex at p.

to the bisector of Cip . For more details on theta-graphs,see [9].
Let S be a set of n ≥ 3 points in the plane that arein convex position. In the following, when we use thenotation G, we mean one of the graphs Θ4k+2 , Θ4k+3 ,Θ4k+4 and Θ4k+5 . Throughout the paper, we assume
that p and q are two distinct points in S and suppose,
without loss of generality, that q ∈ C0p . Let WO be thewedge with apex at the origin O that isof the unionm−20
all cones CtO with m−1
≤
t
≤
.
Let
W
be
O
4
2
the reflection of WO with respect to the point O. Now,
let UO be a wedge with apex at the origin O such that0
∪ C0O (see Figure 3).
UO = WO
m = 4k + 2

2

m = 4k + 3

Preliminaries

Let m ≥ 3 be an integer, and let θ = 2πm be a real
number. For any integer i with 0 ≤ i < m and a point p
in the plane, let Rpi be the ray emanating from p making
the angle θ × i = 2πi/m with the positive x-axis (theangles are considered in counter-clockwise). Let Cip be
the cone which is constructed by the rays Rpi and Rpi+1 .
Note that we assume that Rpm = Rp0 . For a point r anda cone Cip , we say Cip contains r (or, r ∈ Cip ) if r lies
strictly between Rpi and Rpi+1 , or lies on Rpi+1 . If r lies
on Rpi , then r 6∈ Cip . For a point set S, the theta-graphΘm is constructed as follows. For each point p ∈ S,p
we partition the plane into m cones C0p , C1p , . . . , Cm−1p(see Figure 2). Then, for each cone Ci containing atleast one point of S other than p, let ri ∈ Cip be a pointsuch that |pri0 | is minimum where ri0 is the perpendicular
projection of ri onto the bisector of Cip . Then, we add
the edge (p, ri ) to the graph. We assume that a pair(a, b) is a directed edge. We call the point r the closest
point to p in Cip . For a point q ∈ Cip , the canonicaltriangle Tpq is the isosceles triangle which is constructedby the rays of Cip and the line through q perpendicular

WO

WO

O

O

UO

UO

m = 4k + 5

m = 4k + 4
WO

WO

O

O
UO

UO

Figure 3: The wedges WO and UO for the different values of m.

12

ICCG 2022, Sharif UT, February 24, 2022

3

Angle-monotonicity of theta-graphs

In this section, we show that for any integer k ≥ 1
and any i ∈ {2, 3, 4, 5}, the theta-graph Θ4k+i is anglemonotone with width 90◦ + iθ
4 . To this end, we showthat there is an angle-monotone path between p and q
in G with width 90◦ + iθ
4 . Let P = (p = v0 , v1 , . . . , vl )be the directed path in G such that vi+1 ∈ C0vi is theclosest point to vi , and vl is the last vertex of the pathP that lies in Tpq . Let P̈ be the directed path which
is obtained by reversing the direction of all edges of
P . If vl = q, then obviously P is an angle-monotone
path from p to q with width θ. Then, we are done.
Now, in what follows, we assume that vl 6= q. Suppose,
without loss of generality, that q is below P ∪ C0vl (seeFigure 4). Let Q = (q = a0 , a1 . . . , ag = vl ) be the

P
vl

q

p

Figure 4: The path P .
path constructed by the algorithm Θ-Walk(q, vl ) (seeAlgorithm 1). The path Q is a path between q and vl
in G such that for any ai there exists a cone Cjai suchthat vl ∈ Cjai and (ai , ai+1 ) is an edge of G.
Algorithm 1: Θ-Walk(a, b) (see [9])output: A path between a and b in theta-graphs
1 a0 = a;2 i := 0;
3 while ai 6= b do
4
s := an integer such that b ∈ Csai ;5
ai+1 := a point of Csai ∩ S\{ai } such that(ai .ai+1 ) is an edge of Θk ;6i := i + 1;
7 end
8 return the path (a0 , a1 , . . ., ai );3.1

angle θ with the positive x-axis. Let c1 and c2 be theintersection of `1 and `2 with the sides of the triangle
Tpq which are incident to p (see Figure 5). Based on
y
`1

vl

c1
x

d2
d1

q
p

`2

c2

Figure 5: Illustrating the proof of Lemma 1.
the construction of the path P , the vertex vl−1 lies in
the quadrilateral pc1 vl c2 . Let j be an integer such thatq ∈ Cjvl . Since we assume that q is below P ∪ C0vl , wehave 3k + 2 ≤ j ≤ 4k + 1. Since q ∈ Cjvl , we haveqvl ∈ Cj−(2k+1). Consider the triangle Tqvl . Let x and y
be the two other vertices of Tqvl as depicted in Figure 5.
Let d1 6= vl be the intersection of `1 and Tqvl , and let
d2 6= vl be the intersection of `2 and Tqvl . It is notablethat it is possible that the segment xy completely lieson the line `2 . In this case, we assume that d2 = y.
Now, if any vertex u of the path Q lies in the triangle
4vl yd2 , since vl−1 lies in the quadrilateral pc1 vl c2 , thetriangle quvl−1 contains the vertex vl that contradicts
the convexity of the points. Hence, no vertices of Q lie
in the triangle 4vl yd2 . By similar reasons, no vertices
of Q lie in the triangle 4qvl p. Since C0vl ∩ Tpq does notcontain any point of S, the path Q completely lies inthe triangle 4qd1 vl . Then, for any edge (ai , ai+1 ) of Q,
there is an integer t with j − (2k + 1) ≤ t ≤ 2k such thatai+1 ∈ Ctai . Since 3k + 2 ≤ j ≤ 4k + 1, clearly (ai , ai+1 )lies in the wedge Wai .
Now, we have the following lemma.
Lemma 2 If G = Θ4k+2 , then every edge (x, y) of thepath P ∪ Q̈ lies in the wedge Ux .
Proof. By Lemma 1, every edge (a, b) of Q lies in thewedge Wa . Therefore, every edge (b, a) of Q̈ lies in thewedge Wb0 . On the other hand, every edge (vi , vi+1 ) of0
P lies in the cone C0vi . Since UO = WO
∪ C0O , everyedge (x, y) of the path P ∪ Q̈ lies in the wedge Ux . 
Theorem 3 For any set S of points in the plane thatare in convex position and for any integer k ≥ 1, thegraph G = Θ4k+2 is angle-monotone with width 90◦ + θ2 .

The graphs Θ4k+2 and Θ4k+4

We first prove the following lemma.
Lemma 1 If G = Θ4k+2 , then every edge (ai , ai+1 ) of
the path Q lies in the wedge Wai .
Proof. Let `1 be the horizontal line passing throughvl , and `2 be the line passing through vl that forms an
13

Proof. Consider the points p and q. By Lemma 2, every edge (x, y) of the path P ∪ Q̈ lies in the wedge Ux .
Therefore, the path P ∪ Q̈ is an angle-monotone pathfrom p to q in G with width kθ + θ. Note that forG = Θ4k+2 , the angle of the wedge Ux is kθ + θ. Since5th Iranian Conference on Computational Geometry◦360
θ = 4k+2, we have kθ+θ = 90◦ − θ2 +θ = 90◦ + θ2 . Hence,P ∪ Q̈ is an angle-monotone path with width 90◦ + θ2 .
This completes the proof.
there is a vertex g 6= q of the path P 0 below the path P . (b): all vertices of P 0 are
above the path P . For the case (a), let uh
be the last vertex of P 0 below the path P
and let Q0 be the constructed path by thealgorithm Θ-Walk(p, uh ). Then, the algorithm outputs path P = P 0 ∪ Q̈0 . For thecase (b), first the path Q = Θ-Walk(q, vl ) isconstructed. Then, the algorithm outputs thepath P = P ∪ Q̈.

Similar to the proof of Theorem 3, for G = Θ4k+4 withk ≥ 1, we can prove that the path P ∪ Q̈ is an anglemonotone path from p to q with width (k + 1)θ + θ =90◦ + θ. Note that for G = Θ4k+4 , the angle of thewedge Ux is (k + 1)θ + θ. Hence, we have the following
theorem.
Theorem 4 For any set S of points in the plane thatare in convex position and for any integer k ≥ 1, thegraph G = Θ4k+4 is angle-monotone with width 90◦ + θ.
In [3], Bonichon et al., show that any angle-monotone
graph with width γ < 180◦ is a t-spanner with t =1/ cos γ2 . Hence, we have the following result.

For more details, see Algorithm 2.
Algorithm
Θ4k+3 (p, q)
12
34

Corollary 1 For any set of points in the plane thatare in convex position and for any integer k ≥ 1, thegraphs Θ4k+2 and Θ4k+4 have the stretch factor at most
1/cos π4 + θ4 and 1/cos π4 + θ2 , respectively.
3.2

5
6
7
8
9
10
11

The graphs Θ4k+3 and Θ4k+5

We first assume that G = Θ4k+3 . Here, we present analgorithm that finds an angle-monotone path P between
p and q in G with a constant width. The algorithm is
as follows. It first finds the path P = (p = v0 , . . . , vl )which was introduced earlier. If vl = q, then clearly
P = P is an angle-monotone path with width θ, and weare done. Now, in the following we assume that vl 6= q.
Let a be the topmost vertex of the triangle Tpq and let
b 6= p be the other vertex of Tpq . Let m be the midpointof ab. The algorithm considers the following cases.

12
13
14
15
16
17
18
19
20
21
22
23
24
25

2:

Angle-Monotone-Path-

output: An angle-monotone path between p and q in Θ4k+3
P := ∅;
Compute the path P = (p = v0 , . . . , vl );if vl 6= q thenif q lies on the segment “am” then
Q := Θ-Walk(q, vl );P := P ∪ Q̈;
end
else
Compute the path P 0 = (q = u0 , . . . , us );if P and P 0 have a common vertex w thenR := the path which is formed by the portion of P
from v0 to w followed by the portion of P 0 from w
to q;
P := R;end
else
if there is a vertex g 6= q of the path P 0 below
the path P thenuh := the last vertex of P 0 below P ;Q0 := Θ-Walk(p, uh );P := P 0 ∪ Q̈0 ;endelse
Q := Θ-Walk(q, vl );P = P ∪ Q̈;
end
end
end
end
else
P := P ;end
return P;• Case 1: q lies on the segment am. Now, let
Q = (q = a0 , . . . , vl ) be the path constructed by
the algorithm Θ-Walk(q, vl ). Then, the algorithm
outputs the path P = P ∪ Q̈.

26• Case 2: q lies on the segment bm. Let P 0 = (q =uiu0 , . . . , us ) be the path in G such that ui+1 ∈ C2k+1
and ui+1 is the closest point to ui , and us is the lastvertex of the path P 0 that lies in Tqp . Let b0 be thetopmost vertex of the triangle Tqp and let a0 be thebottommost vertex of Tqp . Let m0 be the midpointof a0 b0 . Since q ∈ C0p , it is easy to see that p lies on
the segment a0 m0 . Now, there are two cases:

In the following, we show that the path P returned
by Algorithm 2 is an angle-monotone path between p
and q with width 90◦ + 3θ
4 . We first prove the following
lemma.

– (I): P and P 0 have a common vertex w. The
algorithm outputs the path R which is formedby the portion of P from v0 to w followed by
the portion of P 0 from w to q.
– (II): P and P 0 do not have any common vertex. Now, consider two following cases: (a):

27
28
29
30

Lemma 5 If q lies on the segment am, then every edge
(ai , ai+1 ) of the path Q = (q = a0 , . . . , vl ) lies in thewedge Wai .
Proof. Let j be an integer such that vl ∈ Cjq . Since weassumed that q is below P ∪ C0vl , we have k + 1 ≤ j ≤2k + 1. Consider the triangle Tqvl . Let x and y be thetwo other vertices of Tqvl as depicted in Figure 6(a). It isnotable that the line passing through p and m is parallelto the line passing through q and y. Then, since q lies on
the segment am, the point p is below the line passing
14

ICCG 2022, Sharif UT, February 24, 2022

through q and y. Hence, because of the convexity ofthe points, no points of Q lie in the triangle 4qvl y.
Consider the lines `1 and `2 , and the points d1 and d2
a
`1

x
vl

d2 d1

q
m

y

p

b

`2

(a) Illustrating the proof of Lemma 5.

Now, we have the following lemma.

a

vi+1
vi

uj

p

Proof. Le uh be the last vertex of P 0 below P . According Algorithm 2, P = P 0 ∪ Q̈0 that Q0 is the constructed
path by Θ-Walk(p, uh ). It is clear that for every edgeui(ui , ui+1 ) of P 0 , we have ui+1 ∈ C2k+1, and therefore
ui+1 0ui ∈ C2k+1 . Hence, (ui+1 , ui ) lies in the wedge Yui+1 .
Let Q0 = (p = a01 , a02 , . . . , a0z = uh ). We claim that every edge (a0i , a0i+1 ) lies in the wedge Ya0i . Since p lieson the segment a0 m0 , by the arguments similar to theproof of Lemma 5, the claim is proved. These show thatif (ci , ci+1 ) be an edge of the path P, it lies in the wedge
Yci .


Lemma 8 If q lies on the segment bm and the paths P
and P 0 do not have any common vertex, and there is novertex g 6= q of the path P 0 below the path P , then everyedge (ri , ri+1 ) of the constructed path P by Algorithm 2lies in the wedge Uri .

mqb(b) Illustrating the proof of Lemma 8.

Figure 6: Illustrating the proofs of Lemma 5 andLemma 8.
as defined in the proof of Lemma 1. By the reasons
similar to the proof of Lemma 1, we can prove that thepath Q completely lies in the triangle 4qd1 vl . Then,for any edge (ai , ai+1 ) of Q, there is an integer t withj ≤ t ≤ 2k + 1 such that ai+1 ∈ Ctai . Clearly, this showsthat (ai , ai+1 ) lies in the wedge Wai .
Now, we prove the following lemma.
Lemma 6 If q lies on the segment bm, then every edge
(ri , ri+1 ) of the path R lies in the wedge Uri .
Proof. According to Algorithm 2, the path R is constructed when the paths P = (v1 , . . . , vl ) and P 0 =(u1 , . . . , us ) have a common vertex. It is clear that forevery edge (vi , vi+1 ) of the path P , we have vi+1 ∈ C0vi ,therefore (vi , vi+1 ) lies in the wedge Uvi . On the other
hand, for every edge (ui , ui+1 ) of P 0 , we have ui+1 ∈
ui+1
u
ui
C2k+1
. Therefore, ui ∈ C4k+2
or ui ∈ C0 i+1 . Hence,the edge (ui+1 , ui ) lies in the wedge Uui+1 . This completes the proof.

S

0
4k+2
O
O
Let YO be a wedge with YO =∪ C2k+1i=3k+2 Ci
0OO( C2k+1
is the reflection of C2k+1
with respect to theorigin O). It is clear that the angle of YO is equal to(k + 1)θ + θ/2. Now, we prove the following lemma.
Lemma 7 If q lies on the segment bm and the paths P
and P 0 do not have any common vertex, and there is avertex g 6= q of the path P 0 below the path P , then everyedge (ci , ci+1 ) of the constructed path P by Algorithm 2lies in the wedge Yci .
15

Proof. Let uj be a vertex of P 0 above the path P .
Let vi be the last vertex of P to the left of uj (seeFigure 6(b)). Since p is to the left of uj , the vertex vi
always exist. Since there is no vertex g 6= q of thepath P 0 below the path P , we have uj−1 = q. Now,
consider the triangle Tvi vi+1 . Since P and P 0 have nocommon vertex, clearly uj 6∈ Tvi vi+1 . Hence, if vi 6= p,
then the triangle 4puj vi+1 contains the vertex vi which
contradicts the convexity of the points. Then, vi = p.
On the other hand, since vl 6= q, we must have vi+1 6∈
Tquj , and therefore vl ∈ Ctq with k + 1 ≤ t < 2k + 1.
Now, by the arguments similar to the proof of Lemma 5,
we can prove that every edge (ai , ai+1 ) of the path Q
lies in the wedge Wai . Hence, it is clear that everyedge (ri , ri+1 ) of the path P = P ∪ Q̈ lies in the wedge
U ri .

Based on Lemmas 5, 6, 7 and 8, any path constructed by
Algorithm 2 is angle-monotone with width (k + 1)θ + θ2 .
360◦
Since θ = 4k+3
, we have (k + 1)θ + θ2 = 90◦ + 3θ
4 . Then,the following theorem holds.
Theorem 9 For any set S of points in the plane thatare in convex position and for any integer k ≥ 1, Θ4k+3
is angle-monotone with width 90◦ + 3θ4 .
By the arguments similar to the proof of Theorem 9,
for G = Θ4k+5 with k ≥ 1, we can prove that the path
P is an angle-monotone path from p to q with width360◦(k + 1)θ + θ2 . Since θ = 4k+1
, we have (k + 1)θ + θ2 =5θ90◦ + 4 . Then, the following theorem holds.
Theorem 10 For any set S of points in the plane thatare in convex position and for any integer k ≥ 1, Θ4k+5
is angle-monotone with width 90◦ + 5θ
4 .
We close this section with the following result.

5th Iranian Conference on Computational Geometry

Corollary 2 For any set of points in the plane that arein convex position, the graphs Θ4k+3 and Θ4k+5 withk ≥ 1 have the stretch factor at most 1/cos π4 + 3θ8
and 1/cos π4 + 5θ
8 , respectively.
4

Theta-graph Θ4

In the following, we present two point sets, one in convex
position and the other in non-convex position, to showthat the graph Θ4 of the point set is not angle-monotone
for any width γ > 0. Let p0 , p2 , p3 and p5 be thevertices of a rectangle with length 2 and width 1 + ,
where  > 0 is a small real number (see Figure 7(a)).
Let p1 and p4 be the midpoints of the segments p0 p2
and p3 p5 , respectively. Now, let P = {p0 , p1 , . . . , p5 }.
p0

p5

p0

p1

1

p4

p2

1

p1

p00

p01

p2

p3
p02

1+

p5

1

p4

1

p3

(a) The point set P .

p05

p04

p03

(b) The point set V = P ∪P 0.

Figure 7: The point sets P and V .
Consider the theta-graph Θ4 on P . It is not hard to seethat the edge set E of Θ4 is
E = {(p0 , p1 ), (p1 , p2 ), (p2 , p3 ), (p3 , p4 ), (p4 , p5 ), (p5 , p0 )}.
Now, since p0 p2 and p3 p5 are parallel, it is obvious thatfor any 0 < γ < 180◦ , any path between p1 and p4 is
not angle-monotone with width γ.
Let P 0 = {p00 , p01 , . . . , p05 } be a copy of point set P
such that the points of P 0 placed below the points of P
as depicted in Figure 7(b). Let V = P ∪ P 0 . It is easy
to see that the edge set F of the theta-graph Θ4 on the
point set V is5

Remarks

In Corollaries 1 and 2, we examined the stretch
factor of the graphs Θ4k+2 , Θ4k+3 , Θ4k+4 and Θ4k+5
when the points placed in convex position. In [4],Bose et al., show that the stretch factor of thegraphs Θ4k+2 , Θ4k+3 , Θ4k+4 and Θ4k+5 are at most
1 + 2 sin(θ/2),cos(θ/4)/ (cos(θ/2) − sin(3θ/4)),
1+
2 sin(θ/2)/ (cos(θ/2) − sin(θ/2))
andcos(θ/4)/ (cos(θ/2) − sin(3θ/4)), respectively.
By comparing theresults of Corollarbdies 1 and 2 withthe results in [4],we find that the results of the corollarc
ies do not improveathe stretch factors
known in [4].
Figure 8: The lower boundIn the following,
for the width of Θ4k+2 .
we indicate whether
the bounds on thewidth presented in Theorems 3, 4, 9 and 10 are tightor not. Consider the graph Θ4k+2 . Figure 8 shows thatthe upper bound on the width presented in Theorems 3
is tight. We place a vertex c close to the lower cornerof Tab that is sufficiently far from the vertex b. We also
place a vertex d close to the upper corner of Tba that is
sufficiently far from the vertex a. Now, the graph Θ4k+2
of four points a, b, c and d is as shown in Figure 8. We
can easily see that each of the paths acb and adb are
angle-monotone with width 90◦ + θ2 − , for some real
number  > 0 that only depends on the distance between c (d) and the lower corner (upper corner) of Tab(Tba ). If  approaches zero, then the width approaches
90◦ + θ2 .
For Theorems 4, 9 and 10, we do not know whether
the bounds for the width is tight or not.
6

Conclusion

In this paper, we showed that for any set of points inthe plane that are in convex position and for any integerk ≥ 1 and any i ∈ {2, 3, 4, 5}, the theta-graph Θ4k+i is360◦
angle-monotone with width 90◦ + iθ
4 , where θ = 4k+i .
Moreover, we presented two sets of points in the plane,
F = E ∪ {(p00 , p01 ), (p01 , p02 ), (p02 , p03 ), (p03 , p04 ), (p04 , p05 ), (p05 , p00 )} one in convex position and the other in non-convex po∪ {(p00 , p5 ), (p01 , p4 ), (p02 , p3 )}.
sition, to show that for every 0 < γ < 180◦ , the graphΘ4 is not angle-monotone with width γ. It is notable
It is obvious that for any 0 < γ < 180◦ , any path bethat our technique in Section 3.2, does not work for Θ5
tween p1 and p4 is not angle-monotone with width γ.
because by the proposed technique, the resulting path P
Now, we have the following theorem.
is angle-monotone with width 90◦ + 5θ
4 . Since for Θ5 ,2π◦◦◦
we have θ = 5 ≡ 72 . Then, 90 + 5θ
4 = 180 . We◦
Theorem 11 For any angle 0 < γ < 180 , the graphconjecture for any set of points in convex position, Θ5
Θ4 is not necessarily angle-monotone with width γ.
is angle-monotone with a constant width. We tried to16

ICCG 2022, Sharif UT, February 24, 2022

prove our conjecture but we did not succeed. Finally,
we present the following conjecture.
Conjecture 1 For any set of points in the plane thatare not convex position, for any integer k ≥ 1 and anyi ∈ {2, 3, 4, 5}, the theta-graph Θ4k+i is angle-monotone
360◦
with width 90◦ + iθ
4 , where θ = 4k+i .
References[1] D. Bakhshesh and M. Farshi. Angle-monotonicity ofDelaunay triangulation. Computational Geometry,
94:101711, 2021.
[2] D. Bakhshesh and M. Farshi.
On the planeangle-monotone graphs. Computational Geometry,
100:101818, 2022.
[3] N. Bonichon, P. Bose, P. Carmi, I. Kostitsyna,
A. Lubiw, and S. Verdonschot. Gabriel triangulations and angle-monotone graphs: Local routing
and recognition. In Proceedings of the 24th International Symposium on Graph drawing (GD 2016),
pages 519–531, 2016.
[4] P. Bose, J.-L. D. Carufel, P. Morin, A. van Renssen,
and S. Verdonschot. Towards tight bounds on thetagraphs: More is not always better. Theoretical Computer Science, 616:70 – 93, 2016.
[5] K. Clarkson. Approximation algorithms for shortest path motion planning. In Proceedings of the
Nineteenth Annual ACM Symposium on Theory ofComputing, STOC ’87, pages 56–65, New York, NY,
USA, 1987. ACM.
[6] H. R. Dehkordi, F. Frati, and J. Gudmundsson.
Increasing-chord graphs on point sets. Journal ofGraph Algorithms and Applications, 19(2):761–778,
2015.
[7] J. M. Keil. Approximating the complete euclidean
graph. In R. Karlsson and A. Lingas, editors, 1st
Scandinavian Workshop on Algorithm Theory, pages
208–213, Berlin, Heidelberg, 1988.
[8] A. Lubiw and D. Mondal. Construction and local routing for angle-monotone graphs. Journal ofGraph Algorithms and Applications, 23(2):345–369,
2019.
[9] G. Narasimhan and M. Smid. Geometric spanner
networks. Cambridge University Press, 2007.

17

18

ICCG 2022, Sharif UT, February 24, 2022

Guarding Weakly-Visible Polygons with Half-Guards
Hannah Miller Hillberg∗

Erik Krohn†

Alex Pahlow‡

Abstract
We consider a variant of the art gallery problem where
all guards are limited to seeing to the right inside aweakly-visible polygon. Guards that can only see in
one direction are called half-guards. In this paper, wegive a polynomial time approximation scheme for vertex
guarding a weakly-visible polygon with half-guards. We
then show NP-hardness for vertex guarding a weaklyvisible polygon with half-guards.
1

Figure 1: A WV-polygon where p sees q and every pointin the polygon is seen by a point on e = [l, r] or sees apoint on e.

Introduction

An instance of the original art gallery problem takes as
input a simple polygon P . A polygon P is defined bya set of points V = {v1 , v2 , . . . , vn }. There are edges
connecting (vi , vi+1 ) where i = 1, 2, . . . , n − 1. There isalso an edge connecting (v1 , vn ). If these edges do notintersect other than at adjacent points in V (or at v1
and vn ), then P is called a simple polygon. The edges ofa simple polygon give us two regions: inside the polygon
and outside the polygon. For any two points p, q ∈ P ,we say that p sees q if the line segment pq does not
go outside of P . The art gallery problem seeks to finda guarding set of points G ⊆ P such that every pointp ∈ P is seen by a point in G. In this paper, we study
the vertex guarding problem which says that guards
are only allowed to be placed at the vertices V . The
optimization problem is defined as finding the smallest
such G.
1.1

Previous Work

There are many results about guarding art galleries.
Several results related to hardness and approximations
can be found in [1, 5, 6, 10].
Additional Structure. Due to the inherent difficultyin fully understanding the art gallery problem for simple
polygons, there has been some work done guarding polygons with additional structure, see [3, 8] for example. In
this paper we consider weakly-visible polygons that we∗ Department of Computer Science, University of Wisconsin Oshkosh, Oshkosh, Wisconsin, USA hillbergh@uwosh.edu† Department of Computer Science, University of Wisconsin Oshkosh, Oshkosh, Wisconsin, USA krohne@uwosh.edu
Supported by the Faculty Development Sabbatical Program at the
University of Wisconsin - Oshkosh.
‡ Department of Computer Science, University of Wisconsin Oshkosh, Oshkosh, Wisconsin, USA pahloa45@uwosh.edu

19will describe below. Motivated by the fact that manycameras/sensors cannot sense in 360°, referred to as fullguards in this paper, we study guards that can sense in
180°, referred to as half-guards. We restrict the problem
even further by only allowing these half-guards to see tothe right. Even with these restrictions, the problem isdifficult to solve.
1.2

Definitions

A weakly-visible polygon (WV-polygon) P contains anedge e = (l, r) such that every point in P sees at least
one point on edge e. The usual definition of sees saysthat for any two points p and q inside of the polygon, if
the line segment connecting p and q does not go outsideof the polygon, then p sees q. Let p.x be the x-coordinate
for point p. In this paper, for a point p to see a point
q, it must be the case that p.x ≤ q.x, see Figure 1. The
definition of a WV-polygon is slightly modified to saythat it contains an edge e = (l, r) such that every point
in P sees (or is seen by) at least one point on edge e.
1.3

Our Contribution

NP-hardness has been shown for many variants of theart gallery problem. In many of those reductions, guards
are allowed to see in all directions. If the problem isrestricted enough, it can become polynomially time solvable, for example, see [4, 9]. If the polygon is restricted
to be a WV-polygon, restrict guards to be at the vertices
and only allow them to see to the right, we show thateven with these many restrictions, the problem is still
NP-hard.

5th Iranian Conference on Computational Geometry

Figure 2: A WV-polygon that requires Ω(n) half-guards
that see to the right.
Ashur et al. [2] give a polynomial time approximation
scheme (PTAS) for minimum dominating set in terrainlike graphs, which we will describe later. They then showthat several families of polygons have a visibility graphthat is terrain-like. One such family is WV-polygons.
However, their analysis does not imply that the visibility
polygon of vertex guarding a WV-polygon with halfguards is terrain-like. We provide additional observationsin this paper that show the visibility polygon is terrainlike. There are WV-polygons P that can be completely
guarded with one full-guard but require Ω(n) half-guards
considered in this paper, see Figure 2.
The remainder of the paper is organized as follows.
Section 2 provides a PTAS for vertex guarding a WVpolygon using half-guards. Section 3 shows NP-hardness
for vertex guarding a WV-polygon using half-guards.
Finally, Section 4 gives a conclusion and future work.
2

PTAS for Vertex Guarding a WV-Polygon with
Half-Guards

In this section, we show that the visibility graph of a WVpolygon with half-guards is terrain-like. The visibility
graph is a graph G = (V, E) such that V corresponds tovertices in the WV-polygon and the edges E correspondto vertices that can be seen by other vertices. Then we
use Theorem 1 from [2], see Appendix, to show that a
PTAS exists for vertex guarding a WV-polygon withhalf-guards.
Using the definition from [2], a graph G = (V, E) is
terrain-like if one can assign a unique integer from therange [1, |V |], where |V | is the number of vertices in thepolygon, to each vertex in V , such that, if both (i, k)and (j, l) are in E, for any i < j < k < l, then so is (i, l).
Much of the proof from [2] assumes that the WVpolygon lies above the WV-edge by placing guards at l
and r and cutting off the portion of the polygon beneaththe WV-edge, see Figure 3(left). When every vertex
under consideration lies above this WV-edge, the orderclaim holds and the visibility graph is terrain-like. However, consider doing the same thing for a WV-polygon
using half-guards that see to the right. In this case, theremaining portion of the polygon cannot be assumed to
be above the WV-edge. As shown in the shaded partsof Figure 3(right), the regions to the left of the placed
guards are not seen. More so, a guard placed at l will

Figure 3: On the left, a full-guard placed at l and r
cuts off the polygon below the WV-edge. On the right,
the shaded regions are still unseen after half-guards areplaced at l and r.

Figure 4: Example of vx and Lemma 1.
not dominate a guard placed in the shaded region to
the left of l. If the guards were full-guards, these regions would be seen and the l guard would dominate
any optimal guard placed in this region. We show thateven though these portions of the polygon are unseen
and optimal guards can lie in these regions, the visibility
graph connecting vertices to the guards that see them isstill terrain-like.
2.1

Visibility Polygon is Terrain-Like

We will prove that the visibility polygon of the vertices is
terrain-like by using the following modified order claim
in WV-polygons that applies to full-guards as well as
half-guards. Order the vertices walking in clockwiseorder starting from l: (v1 = l, v2 , v2 , . . . , vn = r).
Modified Order Claim: Assume that guards are placed atl and r and then consider the remaining unseen vertices.
If 4 vertices are in order such that a < b < c < d, thenif a sees c and b sees d, then a sees d.
As shown in [2], if all of a, b, c and d lie above the WVedge, then the order claim holds and a sees d. If botha and d are below the WV-edge and both see l or bothsee r, then the same arguments from [2] hold for why amust see d.
The following lemmas are given for WV-polygons that
apply to full-guards. For simplicity of the arguments, we
assume that the WV-edge is parallel to the x-axis. Letvx be the vertex such that every vertex [vx+1 , vn−1 ] isbelow the WV-edge. If no vertex meets this requirement,
then vx = vn = r. In other words, vx is the last vertex
that is above the WV-edge when walking clockwise froml to r, see Figure 4(left).

20

ICCG 2022, Sharif UT, February 24, 2022

Returning to the discussion with respect to half-guards.
Lemma 5 applies to full-guards. A modification ofLemma 5 is given to apply to half-guards:
Lemma 6 If the order claim is broken, then at least
one of a, b, c or d is seen by either l or r.

Figure 5: If a is blocked from d, then the blocker mustbe either l or r.
Lemma 1 If vi ∈ [v1 , vx ], then no vertex vk ∈ [vi+1 , vn ]can block vi from l.
Proof. Assume that vk blocks vi from seeing l. If thishappens, then vk is to-the-left (when looking from l)of the lvi line segment, see Figure 4(right). Let x be
any point on the WV-edge that vi sees. The xvi line
segment is to the right (when looking from l) of thelvi line segment. This line segment is also blocked by
vk which means vi does not see any point on the WVedge. The polygon is not weakly-visible and we have acontradiction.
□
Corollary 2 Let vw be the vertex such that every vertex[v2 , vw−1 ] is below the WV-edge. If no vertex meets thisrequirement, then vw = v1 = l. If vi ∈ [vw , vn ], then novertex vk ∈ [v1 , vi−1 ] can block vi from r.
Lemma 3 Consider 4 vertices in a WV-polygon suchthat a < b < c < d, a sees c, b sees d and a does notsee d. If a is below the WV-edge and d is above theWV-edge, then a and d must both see l.
Proof. Since a is below the WV-edge, a must see l. If
a does not see l, then the polygon is not weakly-visible.
If d does not see l, then by Lemma 1, the vi blocker
for d must lie in the (l, d) range. If vi ∈ (b, d), then vi
would block b from d. If vi = (a, b], then a would notsee c. It is not possible for vi = a since a is below theWV-edge. Lastly, if that vertex vi ∈ (l, a), then it would
block a from seeing l, see Figure 5(left). Since there is
no way to block d from l, d must see l.
□Corollary 4 Consider 4 vertices in a WV-polygon suchthat a < b < c < d, a sees c, b sees d and a does notsee d. If a is above the WV-edge and d is below theWV-edge, then a and d must both see r.
This brings us to our final Lemma with full-guards:

The complete proof of Lemma 6 is given in the appendix. In short, if the order claim is broken, at least
one of a, b, c or d must lie to the right of l or r and will
necessarily be seen by one of l or r.
The analysis from [2] is now used to show a PTAS
exists. First, one checks to see if the polygon can be
guarded with a constant number of guards of some appropriate size. If an optimal guarding set of this size
does not exist, then the first step of the algorithm is toplace guards at l and r and remove the vertices that lor r see from consideration as they are already guarded.
By Lemma 6, an order claim violation is not possible
since at least one of the vertices involved in breaking theorder claim has already been guarded by l or r and will
not be in the modified problem instance. In other words,
the visibility graph connecting vertices to the guards
that see them are vertices that are not seen by l nor r.
Since the order claim cannot be broken, when looking at
the visibility graph of vertices connected to the leftmost
and rightmost guards that see them, if i < j < k < l,(i, k) ∈ E and (j, l) ∈ E, then (i, l) ∈ E. With this claim,
the visibility graph for vertex guarding WV-polygons
with half-guards that see to the right is terrain-like.
It should also be noted that the orientation of thepolygon does not matter. For example, consider a polygon where the WV-edge is parallel to the y-axis andthe “main” part of the polygon is to the right of the
WV-edge, see Figure 6(left). In this instance, guards
placed at l and r still cause the order claim to not be
broken in the unguarded vertices that remain. Figure 6
shows polygons where the order claim will not be broken.
No matter the orientation of the WV-edge, Lemma 6
holds for half-guards as well as full-guards.
Since the visibility graph is terrain-like, we use Theorem 1 from [2] to state the following:
Theorem 7 There exists a PTAS for vertex guarding a
weakly-visible polygon with half-guards where half-guards
can only see to the right.

3

Lemma 5 If the order claim is broken, then a sees
either l or r and also, d sees either l or r.
Proof. If a < b < c < d, a sees c, b sees d, a does notsee d and a and d are both below the WV-edge, thena sees l and d sees r. This, along with Lemma 3 andCorollary 4, cover the remaining cases.
□
21

NP-hardness for Vertex Guarding a WV-Polygon
with Half-Guards

In this section, we provide a sketch for showing thatvertex guarding a WV-polygon with half-guards is NPhard. NP-hardness for terrain guarding with full-guards
was shown in [7], however, the entire terrain is not seen if
guards are only allowed to look down. In the appendix,

5th Iranian Conference on Computational Geometry

Figure 6: Shows the portion of the polygon “below” theWV-edge that is not seen by l or r.

see to the right. Such a proof works for all instances
except when the WV-edge is parallel to the y-axis andthe “inside” of the polygon is to the left of the WV-edge.
Whether or not this problem is NP-hard is left as an open
problem. Future work might include finding a better
approximation for the point guarding version of thisproblem. Insights provided in this paper may help withguarding polygons where the guard can choose to see
either left or right, or in other natural directions. One
may also be able to use these ideas when allowing guards
to see 180° but guards can choose their own direction,i.e. 180°-floodlights.
References[1] A. Aggarwal. The art gallery theorem: its variations, applications and algorithmic aspects. PhD
thesis, The Johns Hopkins University, 1984.
[2] S. Ashur, O. Filtser, M. J. Katz, and R. Saban.
Terrain-like graphs: Ptass for guarding weaklyvisible polygons and terrains. Computational Geometry, 101:101832, 2022.

Figure 7: An overview of NP-hardness for WV-polygons.

[3] P. Bhattacharya, S. Ghosh, and B. Roy. Approximability of guarding weak visibility polygons. Discrete
Applied Mathematics, 228, 02 2017.

we provide several new and updated gadgets to the
reduction from [7] to show that vertex guarding a terrain
with half-guards that only look down is NP-hard.
We will show how to use the terrain guarding hardness
result for guards that only see down to show that vertex
guarding a WV-polygon with half-guards that see tothe right is NP-hard. One can take the modified terrain
reduction, rotate it counterclockwise 90° and connect
vertex l to vertex r to create a WV-polygon that isvisible from the edge e = (l, r), see Figure 7(left). The
reduction holds the same way that it does for vertex
guarding a terrain with half-guards that only see down.
One will notice that when the WV-edge is rotatedslightly counterclockwise, the reduction still holds, see
Figure 7(right). The key visibilities from the guards
remain and the polygon is still weakly-visible. The reduction begins to fail whenever a guard visibility fromthe original reduction starts to have a negative slope. If
this happens, the guard no longer sees the distinguishedpoint(s) to its right. To account for this, the originalterrain is “stretched” such that none of the guard visibilities have a negative slope. Details of this stretchingare in the appendix.
4

Conclusion and Future WorkIn this paper, we present a PTAS for vertex guarding
WV-polygons with half-guards that see to the right.
This algorithm works regardless of the orientation of the
WV-edge. We also present an NP-hardness proof forvertex guarding a WV-polygon with half-guards that[4] M. C. Couto, P. J. de Rezende, and C. C. de Souza.
An exact algorithm for minimizing vertex guards on
art galleries. Int. Trans. Oper. Res., 18(4):425–448,
2011.
[5] S. Eidenbenz. Inapproximability results for guarding
polygons without holes. In ISAAC, pages 427–436,
1998.
[6] S. K. Ghosh. On recognizing and characterizing
visibility graphs of simple polygons. Discrete &Computational Geometry, 17(2):143–162, 1997.
[7] J. King and E. Krohn. Terrain guarding is np-hard.
SIAM J. Comput., 40(5):1316–1339, 2011.
[8] E. Krohn and B. J. Nilsson. Approximate guardingof monotone and rectilinear polygons. Algorithmica,
66(3):564–594, 2013.
[9] A. Kröller, T. Baumgartner, S. P. Fekete, and
C. Schmidt. Exact solutions and bounds for generalart gallery problems. ACM J. Exp. Algorithmics,
17, may 2012.
[10] D. T. Lee and A. K. Lin. Computational complexity of art gallery problems. IEEE Trans. Inform.
Theory, 32(2):276–282, March 1986.
[11] D. Lichtenstein. Planar formulae and their uses.
SIAM J. Comput., 11:329–343, 1982.

22

ICCG 2022, Sharif UT, February 24, 2022

Appendix
Theorem 1 from [2]Theorem There exists a PTAS for (general) minimum
dominating set in terrain-like graphs. That is, for any
ϵ > 0, there is a polynomial-time algorithm which, givena terrain-like graph G = (V, E) and two sets C, W ⊆ V ,returns Q ⊆ C such that Q dominates W and |Q| ≤(1 + ϵ) · OP T ; here OP T is the size of a minimum subset
of C that dominates W .

Figure 8: The left shows an overview of the NP-hardness
reduction for terrain guarding. The middle is a variablegadget. The right is a starting gadget.

Proof of Lemma 6
Proof. We break up this proof into several cases.

NP-hardness for Vertex Guarding a Terrain with HalfGuards

1. If a and d are both above the WV-edge, then theorder claim cannot be broken as shown in [2].
2. If a is below the WV-edge and d is above the WVedge, then by Lemma 3, a and d see l. It also
must be the case that a and d are to the left of l(otherwise l would see one of them). Since a seesl, d sees l, a sees (or is seen by) c and b sees (or isseen by) d, the entire ad line segment is surroundedby visibility lines that cannot be pierced. Therefore,a must see (or be seen by) d, a contradiction thatthe order claim was broken. Since a and d cannot
both be to the left of l, it must be that l sees oneof them.
3. If a is above the WV-edge and d is below the WVedge, then by Corollary 4, r sees (or is seen by) aand d. In order for r to not see a or d (and rather
be seen by both a and d), both must be to the leftof r. If b or c are below the WV-edge, then r will
see them. Therefore, b and c must be above theWV-edge. Since d sees b, it must be the case thatb is to the right of r. Since b is above and to theright of r, there must be a vertex that blocks r fromseeing b. By Corollary 2, the blocker for r to b must
be in the (b, r) range. If the blocker is in the (b, d)range, then d would not see b. If the blocker is in the(d, r) range, then d would not see r, a contradictionthat the polygon is weakly-visible. It must be thecase that r sees b.
4. If a and d are both below the WV-edge, a is to theleft of l and d is to the left of r, then in order for dto see b, it must be the case that the db line segment
goes below r forcing b to be to the right of r. Similar
to case 3, r sees b. Although not necessary for the
proof, using similar arguments, one can show that lsees c.
□23

Abusing notation, only in this section, we will assume
that half-guards can only see “down.” If we restrict
guards to be half-guards that see “down” in the terrain,
then the terrain guarding problem is still NP-hard. In
regular terrain guarding, a point p sees another point q
if the line segment connecting p and q does not go below
the terrain. In this half-guard variant, the point p sees q
only if the y-coordinate of p is greater than or equal to
the y-coordinate of q and the line segment connecting p
and q does not go below the terrain.
Sketch of Reduction
The terrain guarding reduction is from PLANAR 3SAT
[11] where an instance has n variables and m clauses.
The reduction works by assigning vertices on the terrain
to truth values of variables from the PLANAR 3SAT
instance. For each variable in the PLANAR 3SAT instance, variable gadgets are created such that the gadget
contains a vertex representing xi and vertex representing xi , see Figure 8(middle). These variable gadgets
are grouped together in chunks on the terrain. Figure8(left) shows an example of one such chunk that contains
one variable gadget for each variable in {x1 , x2 , . . . , xn }.
These chunks are replicated on the terrain such that a
guard placed at the xi vertex in the variable gadget ofxi in chunk Cj would require a guard to be placed at thexi vertex in another variable gadget in a different chunk
Ck , see Figure 10 for an example of such mirroring ofdata. There are points on the terrain that correspondto clauses of the PLANAR 3SAT instance. For example,
if clause ci = (xi+1 ∨ xi+3 ∨ xi+4 ) were in the original
PLANAR 3SAT instance, then a point on the terrain
would exist that is seen by three vertices corresponding
to xi , xi+3 and xi+4 . If one of those vertices has a guard
placed on it, then the clause would be satisfied. If noneof those vertices has a guard placed on it, then an extra
guard would be required to guard the terrain. If someminimum number of guards were placed and the entire

5th Iranian Conference on Computational Geometry

Figure 9: To ensure the entire terrain is seen, a guard
is placed at e to see vertices f and g along with the uregion.

Figure 10: The variable gadget remains unchanged from
[7].

terrain was seen, then the original instance was satisfied.
If not, then the original instance was unsatisfiable.
The interested reader is encouraged to read [7] to see
the full details of the original reduction. We modify thegadgets from [7] and show how these modified gadgets
work for guards that can only see down.
Terrain Hardness Modifications
We describe the changes to the gadgets of [7] that must
be made in order for the reduction to hold. Each partwill explain why the original gadget doesn’t work forthis half-guard variant and what changes must be madein order to have the reduction hold.
Between Chunks: Let us order the chunks from top
to bottom (C1 , C2 , . . . , Cm ). We will assume that all
variables gadgets in chunk Ci are below all variablegadgets in chunk Ci−1 . In the original reduction, theterrain between Ci the Ci+2 is seen by any guard placedin the Ci+1 chunk. Since guards can only see down inthis variant, a portion of the terrain, which we will callu, below the lowest variable gadget in Ci and above
the highest variable gadget in Ci+1 will be unseen, see
Figure 9. To fix this, we place a new gadget on theother side of the terrain from Ci . This gadget is at thesame y-coordinate of the lowest variable gadget in chunk
Ci . This ensures that the new guard will not affect themirroring. The vertices f and g can only be seen fromvertex e. Placing a guard at e will see f and g and also
see the unseen region u below chunk Ci .
Variable Gadget: The variable gadgets, shown in Figure
10, do not need to be tweaked much to work. Assume
the xi vertex in the variable gadget in chunk Cj has aguard placed on it and it sees b. In this case, a guard isplaced at xi in the variable gadget in chunk Cj+1 to seea and c. The entire xi variable gadget in chunk Cj+1
is seen. Likewise, if a guard placed at xi in chunk Cjsees a, then a guard is placed at xi in chunk Cj+1 sees b
and c. A small portion of the terrain below xi in chunk

Figure 11: The overview of the terrain reduction whereguards see down.
Cj+1 may have been missed, see Figure 10. However, if
the xi vertex in chunk Cj is lowered just slightly, thenthe guard placed at xi in Cj will see this region andan additional guard is not required. One must ensure
the previously placed xi does not see b but it can see
anything in this gadget above b. Therefore, we ensurethat xi in the previous variable gadget is placed in sucha way that it blocks xi from seeing just above b in thesubsequent variable gadget.
Removing a Variable: We will assume we are removing
a variable from chunk Ci . When a variable gadget isremoved going upwards, the gadget is modified slightly
to remove the a and b vertices. Such a gadget is also
called a starting gadget. When a guard is placed atthe “lower” vertex in this gadget, a small portion of theterrain below the “higher” vertex remains unseen. In
Figure 8(right), a starting gadget is shown. A guard
placed at xi would not see the small portion of theterrain below the xi guard. To ensure this region is seen,
we look at the variable patterns placed in the chunkabove it, chunk Ci−1 . The guard placed in the lowest
variable pattern will see all of these potentially unseen
portions. For example, in Figure 11, the guard placed in
the variable gadget, xk , directly above the rl point will
see all of these unseen regions in the variable patterns
between lr and the variable gadget for xk in chunk C2 .
Therefore, no modification is needed and no additional
24

ICCG 2022, Sharif UT, February 24, 2022

Figure 12: The inversion gadget for variable xi in chunk
Cj+1 . This gadget is not tweaked but the variable gadget
xi in chunk Cj is modified slightly.
guard is needed.
When removing a variable going down, the variablegadget is simply removed. The guard placed in theprevious chunk’s lowest variable gadget will see thisregion. If the lowest variable was being removed, thenthe e guard in the gadget that sees between chunks will
see this region (see Figure 9).
Above chunk C1 and C2 : Since guards cannot see “up,”a guard must be placed that guards the terrain above
the first set of variable gadgets in chunk C1 and above
the variable gadgets in C2 . Assume WLOG that C1 ison the left side of the terrain. Two guards are placedat points l and r as shown in Figure 11. These guards
are required to see their own set of distinguished points,
namely ll , lr , rr and rl . They see the “top” of the terrain
above chunks C1 and C2 . Since all gadgets in chunk
C1 are starting gadgets, rl is placed below chunk C1 toensure the relevant part of the terrain in the starting
gadgets and the terrain above the chunk are seen.
Clause Gadgets: No change is needed for the clausegadgets. All points in the clause gadgets are seen by theappropriate vertices above it.
Inversion Gadgets: A small update is needed for the
inversion gadgets. See Figure 12 for a sample inversion
gadget placed in chunk Cj+1 . If a guard from the variablegadget xi in chunk Cj sees point p, then when guards
are placed at xi1 and xi2 , the entire gadget is seen. If
the guard from chunk Cj guard sees point q, then guards
are placed at xi1 and xi2 . This leaves a small portionof the terrain unseen, the line segment e in Figure 12.
To fix this, similar to the tweak of the variable gadget,the previously placed guard in chunk Cj is tweaked suchthat it sees just over the xi1 guard. In this example,
the previously placed guard must see q and not see p.
As long as it is blocked from p, this is all that matters.
Therefore, it can be tweaked to see the e line segment.
Putting it all together: As seen above, certain tweaks
and updates are made to ensure that the entire terrain
is seen. Making these changes will cause the minimum
25

Figure 13: A stretched WV-polygon such that the NPhardness result holds.
number of guards that must be placed, k, to increase by
m + 1. An additional m − 1 guards are needed to see theunseen regions between chunks. Two additional guards
are added at l and r to see the “top” of the terrain. This
gives us a total of m − 1 + 2 = m + 1 additional required
guards. None of these additional required guards see anyof the original distinguished points of the terrain. They
see their own set of distinguished points and also see theportion of the terrain that would have been unseen. As
shown in [7], if k guards can guard the entire terrain,
the instance is satisfiable. If more than k are needed,
then the instance is not satisfiable.
Theorem 8 Finding the smallest vertex guard coverfor guarding a terrain using half-guards that see down is
NP-hard.
Stretching WV-Polygon Hardness
An example of this stretching is seen in Figure 13(left).
As seen in the example, the original bottom of the terrain
is pulled up and to the right to ensure the polygon
remains weakly-visible and all important lines of sight
look to the right. The l and r vertices are tweaked slightly
to ensure they also see their respective distinguishedvertices to the right.
This stretching of the polygon works even if the WVedge has a positive slope, see Figure 13(right). The
polygon can continue to be stretched as far up and rightas necessary. However, the tweak fails when the WVedge is a vertical edge and the inside of the polygon is tothe left of the edge. We leave this as an open problem.

26

ICCG 2022, Sharif UT, February 24, 2022

A Randomized Algorithm for Non-crossing Matching of Online Points
Shahin Kamali∗

Pooya Nikbakht†

Abstract
We study randomized algorithms for the online noncrossing matching problem. Given a sequence of n online points in general position, the goal is to create amatching of maximum size so that the line segments
connecting pairs of matched points do not cross. In
previous work, Bose et al. [CCCG 2020] showed that asimple greedy algorithm matches at least ⌈2n/3−1/3⌉ ≈0.6̄n points, and it is the best that any deterministic
algorithm can achieve. In this paper, we show that randomization helps to achieve a better competitive ratio,that is, we present a randomized algorithm that matches
at least 235n/351 − 202/351 ≈ 0.6695n points.
1

Introduction

In the geometric matching problems, the input is a setof geometric objects, and the goal is to create a pairwise matching of these objects under different restrictions and objectives. In the bottleneck matching problem, for example, the goal is to create a perfect matching of n points, assuming n is even, so as to minimize
the maximum length of the line segments that connect
matched pairs [8]. Using the same terminology as ingraph theory, we refer to the line segments that connect
pairs of matched vertices as the edges of the matching.
Other variants of the geometric matching problems ask
for perfect matchings that minimize the total length ofedges [4] or maximize the length of the shortest edge
[6]. Matching objects other than points are also studied(see, e.g., [1, 2])
In the non-crossing matching problem, the input is aset of points in general position, and the goal is to match
points in a way that the edges between the matchedpairs do not cross. In the offline setting, it is rather easy
to solve the problem: one can sort all points by theirx-coordinate and match pairs of consecutive points. All
points, except possibly the last one, will be matched.
The running time of this algorithm is O(n log n), whichis asymptotically optimal [5]. Other variants of noncrossing matching have been studied in the offline set∗ Department of Computer Science, University of Manitoba,
Winnipeg, Canada, shahin.kamali@umanitoba.ca† Department of Computer Science, University of Manitoba,
Winnipeg, Canada, nikbakhp@myumanitoba.ca‡ Department of Computer Science, University of Manitoba,
Winnipeg, Canada, sajadpoa@myumanitoba.ca

27

Arezoo Sajadpour‡ting (see [7]). For example, Aloupis et al. [1] considered
the computational complexity of finding non-crossing
matching of a set of points with a set of geometric objects that can be a line, a line segment, or a convex
polygon.
Bose et al. [3] studied the online variant of the noncrossing matching. Under this setting, the input is a setof n points in general position that appear in an online,
sequential manner. When a point x arrives, an online algorithm can match it with an existing unmatched pointy, provided that the edge between them does not crossprevious edges in the matching. Alternatively, the algorithm can leave the point unmatched to be matchedlater. In taking these decisions, the algorithm has no
information about the forthcoming points or the lengthof the input. The algorithm’s decisions are irrevocablein the sense that once a pair of points is matched, thatpair cannot subsequently be removed from the matching. The objective is to find a maximum matching.
Under a worst-case analysis, where an adversary generates the online sequence, it is not possible to match all
points. For example, consider an input that starts withtwo points x and y. If an online algorithm leaves thetwo points unmatched, then the adversary ends the sequence, and the matching is already sub-optimal. If thealgorithm matches x and y, then the adversary generates the next two points on the opposite sides of the line
between x and y, and the matching will be sub-optimalfor this input of length n = 4. Bose et al. [3] extended
this argument to show that in the worst case, no deterministic algorithm can match more than ⌈2n/3 − 1/3⌉
points. Meanwhile, they showed that any greedy algorithm matches at least ⌈2n/3 − 1/3⌉ points, and henceis optimal. An algorithm has the greedy property if itnever leaves a point x unmatched if there is a suitable
unmatched point y that x can be matched to (that is,
the edge between x and y does not cross existing edges
in the matching).
1.1

Contribution

We study randomized algorithms for the non-crossing
matching problem. As in [3], we study worst-case scenarios, where the input is generated adversarially. We
assume the adversary is oblivious to the random choices
made by the algorithm, but it is aware of how the algorithms works (that is, the code of the algorithm).
We present a randomized algorithm that matches at5th Iranian Conference on Computational Geometry

least ⌊235n/351 − 202/351⌋ ≈ 0.6695n points on expectation for any input of size n. This shows the advantage
of randomized algorithms over deterministic ones, whichmatch roughly 0.6̄n points in the worst case.
There are two main components in our randomized algorithm. First, the algorithm maintains a convex partitioning of the plane and matches two points only if they
appear in the same partition. This is followed by updating the partitioning by extending the edge between
the matched pair. This partitioning enables us to use
a simple inductive argument to analyze the algorithm.
Second, the algorithm deviates from the greedy strategy. In particular, the algorithm gives a chance for an
incoming point x to stay unmatched even if there are
one or two points in the same convex region that it canmatch. As we will see, this will be essential for any
improvement over deterministic algorithms.
2

A Randomized Online Algorithm

We present and analyze a randomized online algorithm
for the non-crossing matching problem. In what follows,
for any a ̸= b we use Lab to denote the line passing
through a and b, and Sab to denote the line segment
between a and b.
2.1

Algorithm’s description

The algorithm maintains a partitioning of the plane into
convex regions and matches points only if they belong
to the same region. In the beginning, there is only one
region that is formed by the entire plane. After four
points appear inside a convex region, one or two pairs of
points are matched, and the convex region is partitioned
into two or three convex regions by extending the line
segments passing through the matched pairs.
Let x, y, z, and w be the first four points inside aconvex region C in the same order. In what follows, we
describe how these four points are treated.
• Upon the arrival of x, there is no decision to make,given that there is no point inside C to be matchedwith x.
• Upon the arrival of y, it is matched with x witha probability of 1/2 and stays unmatched with aprobability of 1/2.
• Upon the arrival of z, if the pair (x, y) is alreadymatched, then there is no decision to make. Otherwise, z is matched with x with a probability of
1/3, with y with a probability of 1/3, and stays
unmatched with a probability of 1/3.
• Upon the arrival of w, there are two possibilities toconsider:– First, suppose a pair of points a, b ∈ {x, y, z}
is already matched, while a third point c ∈{x, y, z}/{a, b} is unmatched. If it is possible to match w with c (that is, Swc does notcross Sab ), then w is matched with c; otherwise, when Swc and Sab cross, there is no decision to make.
– Second, suppose no pair of the first threepoints are matched. Then w is matched witha point a ∈ {x, y, z} so that the two points
b, c ∈ {x, y, z}/{a} appear on different sidesof the line Law (if there is more than one such
point, w is matched with z).
After the arrival of four points inside C, either all
points are matched into two pairs, in which case we
say a “double-pair is realized”, or only two points arematched while the other two appear on different sidesof the matched pair, in which case we say a “single-pairis realized”. If a single-pair is realized, in this case, Cis partitioned into two convex regions. If a double-pairis realized, then algorithm extends the line segments
between the matched pairs until they hit the boundary of C or the (non-extended) segment between theother matched pair. This is followed by extending theline segment between the second pair until it hits theboundary of C or extended line that passes through thefirst matched pair. When a double-pair is realized, C ispartitioned into three convex regions.
Assume n ≥ 8. A single-pair is “good” if, after theappearance of all n points, both of the two regions resulted from extending the line segment of the matchingcontain at least 2 points, and it is “bad” otherwise. A
double-pair is said to be “good” if, after the appearanceof all n points, one of the three regions formed by extending the line segments of the two matchings is empty;
otherwise, it is “bad”. The presence of 2 or more than 2points, or no points in a region provides a possibility ofmatching all pairs; hence we assert that a single/double
pair is “good” or “bad” as specified above.
The following example illustrates the algorithm’s
steps. Consider an input formed by 10 points labeledfrom p1 to p10 in the order of their appearance, as depicted in Figure 1. The convex regions maintained by
the algorithm are highlighted in different colors. Initially, the entire plane is a convex region C0 , where point
p1 appears. Upon the arrival of p2 , the algorithm match
it with p1 with a probability of 1/2. Suppose (p1 , p2 ) arematched. Then, there is no decision to be made for p3 .
Upon the arrival of p4 , the line segments Sp1 p2 and Sp3 p4
do not cross. Therefore, p4 is matched with p3 . At thispoint, four points have appeared in C0 and a doublepair (p1 , p2 ) and (p3 , p4 ) has been realized. Therefore,
C0 is partitioned into three smaller convex regions C1 ,C2 , and C3 by extending Sp1 ,p2 and then Sp3 ,p4 (Figure 1a). Points p5 and p6 appear respectively in C3 and28

ICCG 2022, Sharif UT, February 24, 2022

C1

We use an inductive argument to prove f (n) ≤ cn +d where c = 116/351 ≈ 0.3304 and d = 32c − 10 =202/351 ≈ 0.5754. First, we apply Lemma 1 to establish
the base of induction in the following theorem.

C2

p3
p2

p4
p1

Lemma 2 (appendix) For n ∈ [2, 7], it holds thatf (n) ≤ cn + d where c = 116/351 and d = 202/351.
C3

Lemma 3 For n ≥ 8, after serving the first four points
inside a convex region, at least one of the followings
hold:(a) The state of the algorithm after processing p1 , . . . , p4 .
C1

p9

p3
p4
p1

C5

C2

p6
p2

• A good single-pair is realized with a probability ofat least 1/6

p10• A good double-pair is realized with a probability ofat least 1/6.

p5
p7
p8
C4

(b) The state of the algorithm after processing p1 , . . . , p10 .

Figure 1: One possible output of the algorithm when the
input is a sequence of 10 points labeled as p1 , . . . , p10 in
the order of their appearance.
C2 . Since these are the first points in their respective
regions, there is no decision to be made, and they stay
unmatched. Subsequently, p7 appears in C3 and thealgorithm matches with p5 with a probability of 1/2.
Suppose these two points are not matched. Upon thearrival of p8 in C3 , it is matched with p5 or p7 , eachwith a probability of 1/3, and is left unmatched with aprobability of 1/3. Suppose (p5 , p8 ) are matched. Next,
point p9 appears in C2 and is matched with p6 with aprobability of 1/2, and stays unmatched with a probability of 1/2. Suppose (p6 , p9 ) are matched. Finally,
point p10 appears on C3 . Given that the Sp7 p10 crosses
Sp5 p8 , there is no decision to be made, and p10 stays
unmatched. At this point, four points have appeared in
C3 , and a single-pair (p5 , p8 ) has been realized. Therefore, C3 is partitioned into two smaller convex regions
C4 and C5 by extending Sp5 ,p8 (Figure 1b).
2.2

Algorithm’s analysis

Let f (n) denote the expected number of unmatchedpoints left by the algorithm when input is formed by nitems. We use an inductive argument to find an upperbound for f (n). First, we prove the following lemma.
The proof is based on case analysis, and can be foundin the appendix:
Lemma 1 (appendix) We have f (0) = 0, f (1) = 1,
f (2) = 1, f (3) = 4/3, f (4) ≤ 4/3, f (5) ≤ 5/3, f (6) ≤20/9, and f (7) ≤ 52/18.
29

Proof. (sketch) We provide a sketch of the proof here.
The detailed proof can be found in the appendix. Let
x, y, z, and w denote the first four points in the sameorder that they appear.
First, suppose the convex hull formed by the four
points is a triangle ∆. If w is inside ∆, then the pairs(x, y) and (w, z) form a double-pair that is realized witha probability of 1/2. If this is bad, then there should be
at least one future point on each side of the line passing
through (w, z), which means (w, z) is a good single-pair.
We note that the single-pair formed by (w, z) is realizedwith a probability of 1/6. Next, suppose w is a vertex of∆ and another point c ∈ {x, y, z} is inside ∆. Let a, b be
the other two points in {x, y, z}. Then, the pairs (a, b)and (c, w) form a double-pair which is realized with aprobability of at least 1/6. If this double-pair is not
good, then (w, z) is a good single-pair which is realizedwith a probability of 1/6.
Next, suppose the convex hull formed by the four
points is a quadrilateral and includes all of them as
its vertices. In this case, each of the two single-pairs
formed by the diagonals of the convex hull is realized
by a probability of at least 1/6. If both of these singlepairs are bad, then all the remaining points in the input sequence must appear in one of the quarter-planes
formed by extending these diagonals. Then, the doublepair formed by the pair of points on the boundary ofthe quarter-plane and the pair of points outside of thequarter-plain form a good double-pair. The probabilityof such a double-pair to be realized is at least 1/6. □We are now ready to prove the main result.
Theorem 4 There is a randomized algorithm that, for
any input formed by n ≥ 2 points, leaves at most cn + d
points unmatched, where c = 116/351 and d = 202/351.
Proof. We use an inductive argument to show that ouralgorithm satisfies the conditions specified in the theorem. For n ≤ 7, the claim holds by Lemma 1. Suppose

5th Iranian Conference on Computational Geometryn ≥ 8, and assume that for any m < n, it holds thatf (m) ≤ cm + d.
First, we claim that the number of unmatched points
is at most cn + d + (2 − 6c) when a bad single-pair isrealized, or a bad double-pair is realized after the first
four points appear. If a bad single-pair is realized, theneither (I) there is one point on one side of the matchedpair and n − 3 > 2 points on the other side, or (II)there is no point on one side of the matched pair andn − 2 > 2 points on the other side. For (I), by the
induction hypothesis, the number of unmatched points
on the side with n − 3 points will be at most f (n − 3) ≤cn − 3c + d. Therefore, the number of unmatched points
is at most f (n−3)+1 ≤ cn−3c+d+1 < cn+d+(2−6c).
The last inequality holds because c < 1/3. For (II), thenumber of unmatched points will be at most f (n − 2) ≤cn+d−2c < cn+d+(2−6c). If a double-pair is realized
which is not good, then one of the followings holds forthe three regions formed by extending the line segments
between the matched pairs:

at most 1/6((cn+d)+(d−2c))+5/6(cn+d+(2−6c)) =cn + d + 1/6(d − 32c + 10) = cn + d. The last equality
holds because d = 32c − 10.
Next, suppose case b) holds, that is, a good doublepair is realized with a probability of at least 1/6, which
implies a bad single-pair or double-pair is realized with aprobability of at most 5/6. In case the good double-pairis realized, by definition, at least one of the three convex regions formed by extending the double-pair will be
empty. For the other two regions, we have the following
cases:i) One region contains n − 6 points, and the other two
regions each contains one point. Note that n − 6 ≥2 since n ≥ 8. By the induction hypothesis, thenumber of unmatched points is at most 2 + f (n −6) = cn + d + (2 − 6c).

iii) Both regions include m ≥ 2 and n − m − 4 ≥ 2
points. In this case, the number of unmatchedpoints will be at most f (m) + f (n − m − 4) ≤cn + d + (d − 4c) < cn + d + (1 − 5c). The lastinequality holds because c + d < 1.

ii) One region contains m ≥ 2 points, another region
contains one point, and the third region containsn − m − 5 ≥ 2 points. The number of unmatchedpoints is at most f (m) + f (n − m − 5) + 1 ≤ cn −5c + 2d + 1 < cn + d + (2 − 6c). The last inequality
holds because c + d < 1.

Therefore, as long as the good double-pair is realized,
the number of unmatched points will be at most cn +d + (1 − 5c). On expectation, we can write f (n) ≤1/6((cn + d) + (1 − 5c)) + 5/6((cn + d) + (2 − 6c)) =cn + d + 1/6(11 − 35c) < cn + d. The last inequality
holds since c > 11/35.
□

iii) One region contains m1 ≥ 2 points, one region contains m2 ≥ 2 points, and the third region contains
m3 = n − m1 − m2 − 4 ≥ 2 points. The numberof unmatched points is at most f (m1 ) + f (m2 ) +f (m3 ) ≤ cn − 4c + 3d < cn + d + (2 − 6c). The lastinequality holds because c + d < 1.

References

In summary, if a bad single-pair or a bad double-pairis realized, the number of unmatched points is at mostcn + d + (2 − 6c), and the claim holds.
By Lemma 3, after the appearance of the first four
points, either a) a good pair or b) a good double-pair
can be realized with a probability of at least 1/6.
Suppose case a) holds, that is, a good single-pair isrealized with a probability of at least 1/6, which implies a bad single-pair or double-pair is realized with aprobability of at most 5/6. In case the good singlepair is realized, there will be m ≥ 2 points on one
side of the line segment connecting matched pair, andn − m − 2 ≥ 2 points on the other side. Therefore, the number of unmatched points will be at mostf (m) + f (n − m − 2) ≤ cn + 2d − 2c = (cn + d) + (d − 2c).
On expectation, the number of unmatched points will be[2] A. Banik, M. J. Katz, and M. Simakov. Bottleneck segment matching. In Proceedings of the 27th Canadian
Conference on Computational Geometry CCCG, 2015.

i) One region is empty, and the other contains n−4 ≥2 points, in which case the number of unmatchedpoints becomes f (n − 4) ≤ cn + d − 4c < cn + d +(1 − 5c). The last inequality holds because c < 1.
ii) One region contains a single point, and the otherone contains n − 5 ≥ 2 points. The number of
unmatched points will be at most f (n − 5) + 1 ≤cn + d + (1 − 5c).

[1] G. Aloupis, J. Cardinal, S. Collette, E. D. Demaine,
M. L. Demaine, M. Dulieu, R. F. Monroy, V. Hart,
F. Hurtado, S. Langerman, M. Saumell, C. Seara, and
P. Taslakian. Non-crossing matchings of points with geometric objects. Comput. Geom., 46(1):78–92, 2013.

[3] P. Bose, P. Carmi, S. Durocher, S. Kamali, and A. Sajadpour. Non-crossing matching of online points. In Proc.
32nd Canadian Conference on Computational Geometry(CCCG), 2020.
[4] A. Efrat, A. Itai, and M. J. Katz. Geometry helps inbottleneck matching and related problems. Algorithmica,
31(1):1–28, 2001.
[5] J. Erickson. https://mathoverflow.net/questions/86906.
https://mathoverflow.net/questions/86906. Accessed:
2020-05-03.
[6] A. Kaneko and M. Kano. Discrete geometry on red andblue points in the plane—a survey. Discrete & Computational Geometry, 25:551–570, 2003.
30

ICCG 2022, Sharif UT, February 24, 2022

[7] L. Lovász and M. Plummer. Matching Theory. AMS
Chelsea Publishing Series. North-Holland, 2009.
[8] P. M. Vaidya. Geometry helps in matching. SIAM J.
Comput., 18(6):1201–1225, 1989.

By Lemma 5, with a probability of at least 1/3, adouble-pair is realized, and with a probability of at
most 2/3, a single-pair is realized. Therefore, we canwrite f (5) ≤ 1/3 · 1 + 2/3 · 2 = 5/3.

• For n = 6, after the first four points appeared, either asingle-pair or a double-pair is realized:

Appendix
In order to prove Lemma 1, we first prove the following
lemma:
Lemma 5 After four points arrived in the convex region C,
with a probability of at least 1/3, a double-pair is realized,
and with a probability of at most 2/3, a single-pair is realized.
Proof. Let x, y, z, and w denote the four points in the sameorder they appear. There are two cases to consider:• Suppose Sxy crosses Swz . With a probability of 1/2, x
and y are not matched. After that, with a probability of
2/3, z is matched to x or y. Without loss of generality,
assume z is matched with x. Given that Sxy crosses
Swz , line segments Sxz and Syw will not cross, implyingthat w is matched to y, and a double-pair is realized.
So, with a probability of at least 1/2 · 2/3 = 1/3, allpoints are matched, and a double-pair is realized.
• Suppose Sxy does not cross Sxz . Then, (x, y) arematched with a probability of 1/2, and after that, (w, z)
are matched, and a double-pair is realized.
□
Using Lemma 5, we can prove Lemma 1:
Lemma 1 We have f (0) = 0, f (1) = 1, f (2) = 1, f (3) =4/3, f (4) ≤ 4/3, f (5) ≤ 5/3, f (6) ≤ 20/9, and f (7) ≤ 52/18.
Proof. Suppose n items appear in a convex region C. The
proof is trivial for n ≤ 2. In what follows, we prove thelemma for other values of n.
• For n = 3, it is possible that all points stay unmatched,which happens when the second point is not matchedwith the first one (with a probability of 1/2), and then
the third point is not matched with any of the firsttwo points (with a probability of 1/3). Therefore, witha probability of 1/6, all three points stay unmatched,and one point stays unmatched with a probability of
5/6. We can write f (3) = 1/6 · 3 + 5/6 · 1 = 4/3.

• For n = 4, using Lemma 5, we can write f (4) ≤ 1/3 ·0 + 2/3 · 2 = 4/3.
• For n = 5, after the first four points appeared, either asingle-pair or a double-pair is realized:– Suppose a single-pair is realized. Then, C is partitioned into two regions, one containing one point
and the other one containing two points. Therefore, it is expected that f (1) + f (2) = 2 points
stay unmatched.
– Suppose a double-pair is realized. Then, the first
four points are matched, and only the fifth pointstays unmatched.
31– Suppose a single-pair is realized. Then, C is partitioned into two regions. Either (i) the fifth or
the sixth points appear on the same region, in
which case one region will have one point, andthe other one will have three points, or (ii) the
fifth and the sixth points appear in different regions, in which case each region contains twopoints. Therefore, it is expected that at mostmax{f (1) + f (3), f (2) + f (2)} = 7/3 points stay
unmatched.
– Suppose a double-pair is realized. Then, at most
2 points (the last two points) stay unmatched.
By Lemma 5, with a probability of at least 1/3, adouble-pair is realized, and with a probability of at
most 2/3, a single-pair is realized. Therefore, we canwrite f (6) ≤ 1/3 · 2 + 2/3 · 7/3 = 20/9.

• For n = 7, after the first four points appeared, either asingle-pair or a double-pair is realized:– Suppose a single-pair is realized. Then, C is partitioned into two regions. Either (i) the fifth, thesixth, and the seventh points all appear in thesame region, in which case one region has one
point, and the other one has four points (Figure 2a), or (ii) one of these points appear in one
region, and the other two appear in the other region, in which case one region contains two points,
and the other region contains three points (Figure 2b). Therefore, it is expected that at mostmax{f (1) + f (4), f (2) + f (3)} ≤ max{1 + 4/3, 1 +4/3} = 7/3 points stay unmatched.
– Suppose a double-pair is realized. Then, at
most three points stay unmatched, which happens
when any of the three regions formed by partitioning of the first four points includes a single point(see Figure 2c).
Unlike other cases, here, the expected number of unmatched points is larger when a double-pair is realized, and hence we cannot use Lemma 5. Instead,
we note that the probability of a single-pair being realized is at least 1/6 This is because a single-pair isrealized if either (i) the first two points are matchedwith a probability of 1/2, and the other two points appear on opposite sides of the line passing through thematched points, happening with a total probability of
1/2, (ii) the first two points are not matched with aprobability of 1/2, and the third point is matched toeither of the first points with a probability of 1/3, andthe fourth point appears on the side of the matchedline that the other unmatched point is not on, happening with a total probability of 1/6, or (iii) the
first three points stay unmatched with a probability of5th Iranian Conference on Computational Geometryd• A good single-pair is realized with a probability of atleast 1/6ca

• A good double-pair is realized with a probability of atleast 1/6.

b

Proof. Let x, y, z, and w denote the first four points in thesame order that they appear.
First, suppose the convex hull formed by the four points
is a triangle ∆ which includes the fourth point inside it. We
consider the following two cases:(a) The case where a single-pair is realized, and the last three points appear indifferent regions.
d• Assume w is the point that is inside ∆. Then the pairs(x, y) and (w, z) form a double-pair that is realized witha probability of 1/2. This is because the pair (x, y) ismatched with a probability of 1/2, and then the pair(w, z) is matched with a probability of 1. Meanwhile,(w, z) is a single-pair which is realized with a probability of 1/6. This is because, with a probability of 1/6,
the first three points stay unmatched, and then the algorithm matches w to z with a probability of 1. Now,
if the double pair formed by the pairs (x, y) and (w, z)
is bad, then there should be at least one future pointon each side of the line passing through (w, z), whichmeans (w, z) is a good single-pair (see Figure 3a).

c

a

b

(b) The case where a single-pair is realized, and the last three points appear indifferent regions.
c

a

b
d

• Assume w is a vertex of ∆ and another point c ∈{x, y, z} is inside ∆. Let a, b be the other two points
in {x, y, z}. Then, the pairs (a, b) and (c, w) form a
double-pair which is realized with a probability of atleast 1/6. This is because the pair (a, b) is matched witha probability of at least 1/6 (the pair (a, b) is matchedwith a probability of 1/2 if z ∈/ {a, b}, and with a probability of 1/6 if z ∈ {a, b}), and then w is matched withc with a probability of 1. Meanwhile, the pair (c, w) isa single-pair which is realized with a probability of 1/6.
Similar to the previous case, if the double pair formedby the pairs (a, b) and (c, w) is bad, then there should
be at least one future point on each side of (a, b), whichmeans (a, b) is a good single-pair (see Figure 3b).

(c) The case where a double-pair is realized, and the last three points appear indifferent regions.

Figure 2: The cases used in the calculation of f (7);a, b, c, d ∈ {x, y, z, w} where x, y, z, and w are the first
four points in the same order of their appearance.
1/2·1/3 = 1/6, and then the fourth point gets match tothe point that bisects the unmatched points, happening
with a total probability of 1/6. Therefore, we can write
f (7) ≤ 5/6 · 3 + 1/6 · 7/3 = 52/18 (see Figure 2).
□

Lemma 2 For n ∈ [2, 7], it holds that f (n) ≤ cn + d wherec = 116/351 and d = 202/351.
Proof. The proof follows from Lemma 1. For n = 2, wehave f (2) = 1 < 2c + d (since 2c + d > 1.2362). For n = 3,
we have f (3) = 4/3 = 3c + d (since 3c + d > 1.5669). For
n = 4, we have f (4) ≤ 4/3 < 4c + d (since 4c + d > 1.8974).
For n = 5, we have f (5) ≤ 5/3 < 5c + d (since 5c + d >2.2279). For n = 6, we have f (6) ≤ 20/9 < 6c + d (since
6c + d > 2.5584). For n = 7, we have f (7) ≤ 52/18 = 7c + d(note that 7c + d = 52/18).
□
Next, we provide the detailed proof of Lemma 3:
Lemma 3 For n ≥ 8, after serving the first four points
inside a convex region, at least one of the followings hold:

Next, suppose the convex hull formed by the four points
is a quadrilateral and includes all of them. Consider thetwo single-pairs formed by the diagonals of the convex hull.
Any of these pairs can be realized with a probability of atleast 1/6. Specifically, the diagonal involving w is realized
when no pair of points from {x, y, z} are matched, whichtakes place with a probability of 1/6. The other diagonal
is either between x and y, which is realized with a probability of 1/2, or between z and a ∈ {x, y}, which is realizedwith a probability of 1/6. Therefore, if any of the two diagonal forms a good single-pair, the statement of the lemma
holds, and we are done (see Figure 3c). If none of the two
diagonals is good, then all the remaining points in the input
sequence should appear in one of the quarter-planes formedby extending these diagonals (see Figure 3d). Then, thedouble-pair formed by the pair of points on the boundaryof the quarter-plane (points b and c in Figure 3d) and thepair of points outside of the quarter-plain (points w and a in
Figure 3d) form a good double-pair. The probability of sucha double-pair to be realized is at least 1/6. This is because
one of the pairs in the double-pair involves two of the first
three points. If these points are (x, y), the double-pair is32

ICCG 2022, Sharif UT, February 24, 2022

w

z

w

x

y

c

a

(a)

b

(b)
c

c
w

w

a

b

(c)

a

b

(d)

Figure 3: An illustration of the proof of Lemma 3. (a)when w is inside the triangle ∆, either the single-pairformed by (w, z) is a good single-pair, or the doublepair formed by (x, y), (w, z) is a good double-pair. (b)when c ∈ {x, y, z} is inside the triangle ∆, either the
double pair formed by (a, b), (w, c) is a good doublepair, or the single-pair formed by (w, c) is a good singlepair. (c) the case when at least one of the diagonals of
the convex hull formed by the four points (here (w, b))forms a good single-pair (d) when none of the singlepairs formed by the diagonals of the convex hull are
good, all remaining points appear in one of the quarterplanes formed by extending these diagonals; therefore,
the pair of points on the boundary of the quarter-plane(here (b, c)) and the pair of points outside the quarterplanes (here (w, a)) form a good double-pair.
realized with a probability of 1/2; otherwise, it is realizedwith a probability of 1/6.
□

33

34

ICCG 2022, Sharif UT, February 24, 2022

Online Square Packing With Rotation
Shahin Kamali∗

Pooya Nikbakht†

Abstract
In the square packing problem, the goal is to place amulti-set of square items of different side lengths in (0, 1]
into a minimum number of square bins of uniform side
length 1. In the online setting, the multi-set of items
forms a sequence that is revealed in an online and sequential manner. When an item is revealed, an online
algorithm has to place it into a square bin without any
prior knowledge of the forthcoming items. All existing
results for the online square packing are restricted to thecase when square items are placed orthogonally to thesquare bins. In this paper, we provide an algorithm withan asymptotic competitive ratio of 2.306 when squares
are allowed to be rotated.
1

Introduction

An instance of the square packing problem is definedwith a multiset of squares-items of different sizes in therange (0, 1]. The goal is to place these squares into aminimum number of unit square bins in a way that twosquares-items placed in the same square bin do not intersect. The problem is a generalization of the classicalbin packing problem into two dimensions. As such, wesometimes refer to the squares-items simply as items
and square bins as bins. A square item can be recognized by the length of its side, which we refer to as thesize of the square.
In the offline setting, all square items are given in advance, and the algorithm can process them as a whole
before placing any item into a bin. In particular, thealgorithm can sort squares in the decreasing order of
their sizes, and this comes in handy in many settings.
In the online setting, the multi-set of items forms a sequence that is revealed in an online and sequential manner. Items are revealed one by one; when an item is revealed, an online algorithm has to place it into a squarebin without any prior knowledge of forthcoming items.
The decisions of algorithms are irrevocable.
Square packing has many applications in practice.
One prominent application is cutting stuck where bins
represent stocks (e.g., wood boards) and items are requests to squares of specific sizes. When requests arrive,∗ Department of Computer Science,

University of Manitoba,
Winnipeg, Canada, shahin.kamali@umanitoba.ca† Department of Computer Science, University of Manitoba,
Winnipeg, Canada, nikbakhp@myumanitoba.ca

35

an algorithm has to ‘cut’ the stock to provide the pieces
that match the requests. This cutting process is equivalent to ‘placing’ items into bins. The goal of cutting
stock is to minimize the number of stocks which also
matches a square packing goal. We note that in many
practical applications, requests arrive in an online manner and the stock should be cut without priory knowledge about the future requests. It is needless to saythat the cutting process is irrevocable which gives aninherently online nature to these applications of square
packing.
There has been a rich body of research around square
packing. To our knowledge, all existing results except
for our previous work on offline square packing [17], assume that squares are not allowed to rotate, that is,sides of square items should be parallel to the squarebins. While this assumption makes combinatorial analysis of the problem easier, might cause a higher cost. As
an example, consider an instance of the problem formedby n items of size 0.36. If we do not allow rotation, any
bin can include at most 4 items, which results a total
cost of n/4 for any algorithm. Allowing rotation, however, 5 items fit in each bin and we can reduce the cost ton/5 (see Figure 1). As a result, the number of requiredbins is decreased by n/20 which is a notable saving inpractice (e.g., for cutting stock applications).
In this paper, we consider the online square packing
problem with rotation which is defined as follows.
Definition 1 In the online square packing with rotation, the input is a multi-set of squares (items) withsizes S = {x1 , ..., xn } where 0 < xi ≤ 1. The goal is topack these squares into the minimum number of squaresof unit size (bins). In the offline setting, S is available
since the beginning. In the online setting, S is revealed
as a sequence σ = ⟨x1 , x2 , . . . , xn ⟩ which is revealed in
an online manner. At time-step t, the value of xt is revealed and an online algorithm has to place a square of√2
Figure 1: If all input items have length 2√2+1≈ 0.35,rotation allows packing 5 items per bin instead of 4.

5th Iranian Conference on Computational Geometry

size x (1 ≤ t ≤ n). The decisions of the algorithm are
irrevocable and are made without knowing the values ofxt′ for t′ > t.

classification and analysis different from the previous
work.

The asymptotic competitive/approximation ratio is
the standard method for analyzing packing problems.
We say an algorithm Alg has a competitive ratio of cif there exists a constant c0 such that, for all n and for
all input sequences σ of length n, we have Alg(σ) ≤c · Opt(σ) + c0 where A(σ) and Opt(σ) denote the costsof A and Opt for processing σ, respectively, and are botharbitrarily large.

2

1.1

Related work

The 1-dimensional bin packing has been studied extensively in both offline and online settings (see, e.g., [14,13, 6, 7]). In the 1-dimensional setting, each item has
simply a size ∈ (0, 1], and each bin has a capacity of 1.
In the offline setting, the problem is NP-hard, and thebest existing result is an algorithm that opens at mostOpt(σ)+O(log Opt) bins for placing a sequence σ [16].
In the online setting, the best existing algorithm has acompetitive ratio of 1.578 [2]. Meanwhile, it is known
that no online algorithm has a competitive ratio better
than 1.54278 [3].
There are many ways to extend bin packing to higher
dimensions (see [5] for a survey). Orthogonal packing square items into square bins is perhaps the moststraightforward extension. In the offline setting, theproblem is known to be NP-hard [18]. Bansal et al. [4]provided an APTAS for this problem (indeed, for the
more general d-dimensional cubes). In the online setting, the best existing upper and lower bounds have
improved a few times [19, 10]. The best existing algorithm has a competitive ratio of 2.0885 [8] while the best
existing lower bound is 1.6707 [15].
In a previous work [17], we studied offline square
packing when the rotation of items is allowed. We
showed that, while the problem remains NP-hard, it
admits an APTAS under a resource-augmentation setting, where bins of the algorithm have size 1 + α, for an
arbitrary small α > 0, while bins of Opt have size 1.
If resource augmentation is not allowed, the problem islikely ∃R-hard [17, 1].
1.2

Contribution

We consider the online setting and provide an online
algorithm that achieves a competitive ratio of 2.306 forthe square packing problem. Our algorithm is basedon classifying squares based on their sizes and placing
squares of similar sizes tightly, possibly using rotations,in the same bins. This approach is previously used to
introduce different families of Harmonic algorithms forbin packing in both one dimension and higher dimensions. The presence of rotations, however, make ourSquare-Rotate algorithm

In this section, we introduce our square packing algorithm called Square-Rotate.
2.1

Item classification

Similar to the Harmonic family of algorithms, we classify squares by the size of their side lengths (which we
simply refer to as the size of the items).
Square-Rotate packs squares of each class separately from other classes. In total, there are 13 classesof squares (having more classes is possible but leads tonone to small improvement of the final result). Square
items with sizes in the range (0, 0.1752] are in class 13.
We refer to class 13 as the tiny class, and items thatbelong to this class are referred to as tiny items. We
refer to items that belong to class i ∈ [1, 12] as regular
items. For each class i ∈ [1, 12], the range of items in
the class is specified as (xi , xi−1 ] (for convenience, we
define x0 = 1). The values of xi ’s are defined in a waythat a certain number of items, denoted by Si , of class i
can fit in the same bin. The specific range of item sizes
for each class i ∈ [1, 12] and values of Si is derived fromthe best-known or optimal results [12] on the congruent
square packing problem [11], which asks for the minimum size c(j) of a square that can contain j unit-sizedsquares. A scaling argument, where the container size
is fixed to be 1, gives values of u(j) when the goal is
to pack j identical squares of maximum size u(j) into aunit square.
In Figure 2, it is specified how Si items of the largest
size in class i can fit into a square bin. Therefore, thescaled best-known values of u(j) for 1 ≤ j ≤ 36 canbe derived from the figure. These scaled numbers givethe specific ranges that we used for classifying items asfollows: Items of class 1 have sizes in the range (1/2, 1],
and we have x1 = 1/2. Note that exactly S1 = 1 item ofclass 1 can fit in the same bin. For i ∈ [2, 12], Si is thenumber of items of size xi−1 that fit in the same bin. For
example, for i = 2, we have S2 = 4 because x1 = 1/2,
and 4 items of size 1/2 fit in the same bin. Moreover,xi is defined as the largest value so that Si + 1 items ofsize xi cannot fit in the same bin. For example, we havex2 = 0.3694 because according to Figure 2, S2 + 1 = 5
squares of size 0.3694 cannot fit in the same bin.
The respective range of items for each class, as well as
the values of Si , are presented in Table 1. For example,
a square belongs to class 1, 2, or 12 if its side size isin the interval (0.5, 1], (0.3694, .5], or (0.1752, 0.1779],
respectively.
36

ICCG 2022, Sharif UT, February 24, 2022

(a)

(b)

Class 1: x ∈(0.5000, 1.0000]

Class 2: x ∈(0.3694, 0.5000]

(g)

(h)

Class 7: x ∈(0.2139, 0.2500]

Class 8: x ∈(0.2073, 0.2139]

(c)

(d)

Class 3: x ∈(0.3333, 0.3694]

(i)

(e)

Class 4: x ∈(0.2697, 0.3333](j)Class 9: x ∈(0.2047, 0.2073]

Class 5: x ∈(0.2579, 0.2697](k)Class 10: x ∈(0.2000, 0.2047]

Class 11: x ∈(0.1779, 0.2000](f)
Class 6: x ∈(0.2500, 0.2579](l)Class 12: x ∈(0.1752, 0.1779]

Figure 2: Placement of regular square items of class i ∈ [1, 12] in their respective bin. It is possible to pack i square
items of class i into a single square bin [12].
Class
1
2
3
4
5
6
7
8
9
10
11
12
13

Side length x(0.5000, 1.0000](0.3694, 0.5000](0.3333, 0.3694](0.2697, 0.3333](0.2579, 0.2697](0.2500, 0.2579](0.2139, 0.2500](0.2073, 0.2139](0.2047, 0.2073](0.2000, 0.2047](0.1779, 0.2000](0.1752, 0.1779](0, 0.1752]

Si
1
4
5
9
10
11
16
17
18
19
25
26

Occupied Area
> 1(0.250)=0.250> 4(0.136)=0.544> 5(0.111)=0.555> 9(0.072)=0.648> 10(0.066)=0.660> 11(0.062)=0.682> 16(0.045)=0.720> 17(0.042)=0.714> 18(0.041)=0.738> 19(0.040)=0.760> 25(0.031)=0.775> 26(0.030)=0.780> 0.702

Weight
1
1/4
1/5
1/9
1/10
1/11
1/16
1/17
1/18
1/19
1/20
1/26
1.425x2

Density< 4.000< 1.838< 1.801< 1.543< 1.515< 1.466< 1.388< 1.400< 1.355< 1.315< 1.290< 1.282≈ 1.425

Table 1: A summary of item classification and details
on item weights and densities, as used in the definition
and analysis of Square-Rotate.
2.2

Packing regular items

For each class i (1 ≤ i ≤ 12), the algorithm has at mostone active bin of type i. When a bin of type i is opened,
it is declared as the active bin of the class, and Si squarespots, each having a size equal to the largest square ofclass i, are reserved in the bin. Upon the arrival of an
item of class i, it is placed in one of the Si spots of theactive bin. If all these spots are occupied by previous
items, a new bin of type i is opened. This ensures thatall bins of type i, except potentially the current activebin, include Si items.
2.3

Packing tiny items

For the last class, i.e., tiny items, the algorithm uses
a different approach, proposed by Epstein and van
Stee [9]. Briefly, it maintains at most one active bin
for placing tiny items. When a bin is opened for these
items, the algorithm reserves four square spots of size
37

1/2, i.e., the four squares of class 2 in Figure 2b. Thesesquare spots are used as bins for placing tiny items.
Then, the algorithm chooses one of the innermost subbin squares that has enough space for the arrived item
and repeats the procedure for the selected sub-bin until it cannot split any of the innermost sub-squares into
four new ones with enough space for the item. At thisstep, the item is placed in one of those smallest subbins. When the next item arrives, if there is a sub-binof the smallest possible size in which the item can fit,
the algorithm places the item in that spot. Otherwise,
the algorithm finds the smallest sub-bin that can fit theitem and repeats the previous procedure to split it into
the smaller sub-bins to reach an appropriate spot for
the item. If no sub-bin with enough empty space isavailable in the bin, the algorithm closes the current
bin and opens a new empty active bin for the item andapplies the whole process from the beginning (see [9],for details). Note that the algorithm does not rotate
any of the tiny items to pack them. Epstein and van
Stee proved the following result, which we will use in
our analysis later.
Lemma 1 [9] Consider the square packing problem(without rotation) in which all items are of size at most
1/M for some integer M ≥ 2. There is an online algorithm (as described above) that creates a packing inwhich all bins, except possibly one, have an occupied
area of size at least (M 2 − 1)/(M + 1)2 .
2.4

Algorithm’s analysis

In this section, we prove a competitive ratio of at most
2.306 for our algorithm. We use a weighting function
argument. For each item of size x, we define a weightw(x) for the item and prove that: (1) the total weight5th Iranian Conference on Computational Geometryof square items in each bin of the algorithm, except
potentially a constant number of them, is at least 1, and(2) the total weight of items in each bin of an optimal
packing is at most 2.306. If w(σ) denote the total weightof items in an input sequence σ, then (1) implies thatthe number of bins opened by the algorithm is at mostw(σ) + c, for some constant value of c, and (2) implies
that the number of bins in an optimal packing is at leastw(σ)/2.306. Therefore, the (asymptotic) competitive
ratio of the algorithm would be at most 2.306.
Recall that all bins opened for squares of class i (1 ≤i ≤ 12), except possibly the last active bin, include Si
squares. We define the weight of items of class i tobe 1/Si . This way, the total weight of items in bins
opened for all squares of classes 1 to 12, except possibly
12 of them (the last bin from each class), is exactly 1.
Therefore, (1) holds for bins opened for regular items.
We define the weight of a tiny square of size x as
x2 /0.701(= 1.425x2 ). All tiny items are of size at most
0.1752. Therefore, by Lemma 1, the occupied area of allbins opened for tiny items (except possibly one of them)will be at least 0.701. This implies their total weight is
at least 0.701/0.701 = 1.
Table 1 gives a summary of the weights of items in
different classes. From the above argument, we conclude
the following lemma.

References[1] M. Abrahamsen, T. Miltzow, and N. Seiferth. Framework for ∃r-completeness of two-dimensional packing
problems. In 2020 IEEE 61st Annual Symposium on
Foundations of Computer Science (FOCS), pages 1014–
1021. IEEE, 2020.
[2] J. Balogh, J. Békési, G. Dósa, L. Epstein, and A. Levin.
A new and improved algorithm for online bin packing.
In 26th Annual European Symposium on Algorithms(ESA), volume 112 of Leibniz International Proceedings in Informatics (LIPIcs), pages 5:1–5:14. Schloss
Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018.
[3] J. Balogh, J. Békési, G. Dósa, L. Epstein, and A. Levin.
A new lower bound for classic online bin packing.
CoRR, abs/1807.05554, 2018.
[4] N. Bansal, J. R. Correa, C. Kenyon, and M. Sviridenko.
Bin packing in multiple dimensions: Inapproximability results and approximation schemes. Mathematics ofOperations Research, 31(1):31–49, 2006.
[5] H. I. Christensen, A. Khan, S. Pokutta, and P. Tetali.
Approximation and online algorithms for multidimensional bin packing: A survey. Computer Science Review,
24:63–79, 2017.
[6] E. G. Coffman, M. R. Garey, and D. S. Johnson. Approximation algorithms for bin packing: A survey. In
Approximation algorithms for NP-hard Problems. PWS
Publishing Co., 1997.

Lemma 2 The total weight of squares in each bin
opened by Square-Rotate, except possibly a constantnumber of them, is at least 1.

[7] E. G. Coffman Jr., J. Csirik, G. Galambos, S. Martello,
and D. Vigo. Bin packing approximation algorithms:
survey and classification. In P. M. Pardalos, D.-Z. Du,
and R. L. Graham, editors, Handbook of Combinatorial
Optimization, pages 455–531. Springer, 2013.

The following lemma provides an upper bound forthe total weight of items in a bin of the optimal offline
algorithm (Opt). The proof works by case analysis andcan be found in the appendix.

[8] L. Epstein and L. Mualem. Online bin packing ofsquares and cubes. arXiv preprint arXiv:2105.08763,
2021.
[9] L. Epstein and R. van Stee. Optimal online bounded
space multidimensional packing. In Proceedings of the
fifteenth annual ACM-SIAM symposium on Discrete algorithms, pages 214–223, 2004.

Lemma 3 The total weight of items in every bin of
Opt is less than 2.306.
Provided with the above two lemmas, we can derive
the main result of this section.
Theorem 4 There is an online algorithm for thesquare packing problem with rotation problem which
achieves a competitive ratio of at most 2.306.
Proof. For an input σ, let SR(σ) and OP T (σ) denotethe cost of Square-Rotate and Opt, respectively. Letw(σ) denote the total weight of items of σ. Lemmas 2
implies that SR(σ) ≤ w(σ) + c, where c is a constant
independent of the length of σ. Meanwhile, Lemma 3
implies that Opt(σ) ≥ w(σ)/2.306. From these inequalities, we conclude SR(σ) ≤ 2.306 OP T (σ) + c, which
proves an upper bound 2.306 for the competitive ratioof Square-Rotate.
□[10] L. Epstein and R. van Stee. Online square and cube
packing. Acta Informatica, 41(9):595–606, 2005.
[11] P. Erdős and R. L. Graham. On packing squares withequal squares. Journal of Combinatorial Theory, SeriesA, 19:119–123, 1975.
[12] E. Friedman. Packing unit squares in squares: A survey
and new results. The Electronic Journal of Combinatorics, pages 1–24, 2000.
[13] G. Galambos and G. J. Woeginger. Online bin packing- a restricted survey. ZOR, 42:25–45, 1995.
[14] M. R. Garey and D. S. Johnson. Approximation algorithms for bin packing problems - a survey. In
G. Ausiello and M. Lucertini, editors, Analysis andDesign of Algorithms in Combinatorial Optimization,
pages 147–172. Springer, New York, 1981.
38

ICCG 2022, Sharif UT, February 24, 2022

[15] S. Heydrich and R. van Stee. Beating the harmonic
lower bound for online bin packing. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Schloss Dagstuhl-LeibnizZentrum fuer Informatik, 2016.
[16] R. Hoberg and T. Rothvoss. A logarithmic additive
integrality gap for bin packing. In proc. the 28th Annual ACM-SIAM Symposium on Discrete Algorithms(SODA), pages 2616–2625. SIAM, 2017.
[17] S. Kamali and P. Nikbakht. Cutting stock with rotation: Packing square items into square bins. In International Conference on Combinatorial Optimization andApplications, pages 530–544. Springer, 2020.
[18] J. Y. T. Leung, T. W. Tam, C. S. Wong, G. H. Young,and F. Y. L. Chin. Packing squares into a square. Journal of Parallel and Distributed Computing, 10(3):271–
275, 1990.
[19] S. S. Seiden and R. van Stee. New bounds for multidimensional packing. Algorithmica, 36(3):261–293, 2003.

Appendix
Lemma 3 The total weight of items in every bin of Opt isless than 2.306.
Proof. We first define the density of an item of size x as
the ratio between its weight and area, i.e., w(x)/x2 . Given
the lower bound for the size of each square belonging toclass i (1 ≤ i ≤ 12), we can calculate a lower bound for thedensity of each item in the class. For tiny items, the density
is simply 1.425x2 /x2 = 1.425. Densities for all classes havebeen reported in Table 1.
Defining densities comes handy in the following case analysis to prove that the total weight of items in any bin B ofan optimal packing is at most 2.306.
Case 1: First, assume there is no item of class 1 in B. Since
the density of items of other classes are less than 1.838, even
if B is fully packed with items of the largest density, thetotal weight of items cannot be more than 1.838 which isless than 2.306.
Case 2: In the second case, we assume there is one itemx of class 1 (note that no two items of class 1 fit in thebin). Without loss of generality, we assume the size of x
is 1/2 + ϵ, where ϵ is a small real value greater than zero.
Clearly, a larger size for x does not increase the total weightof other items in B because it would leave less space tooccupy more items in the bin (while the weight of x stays 1).
Next, we consider all possible cases in which we have someitems of class 2 and 3 together with x in B. As presented inTable 2, there will be 14 sub-cases to analyze. To see how wereach these 14 sub-cases, first note that it is not possible toaccommodate 4 or more items of class 2 in addition to x in
B (i.e., a total number of 5 or more items from these classes
1 and 2). This is because no five items with size larger than
0.3694 can fit in B [12]. A similar argument shows that wecannot have 6 or more items from classes 1, 2, and 3 together
in a bin, otherwise we could accommodate 6 identical squaresof size strictly larger than 0.3333 which is a contradiction to
39

C1

C2

C3

1
1
1
1
1
1
1
1
1
1
1
1
1
1

0
0
0
0
0
1
1
1
1
2
2
2
3
3

0
1
2
3
4
0
1
2
3
0
1
2
0
1

total weightarea occupied

remaining

total weight intotal weight ofof items of

by items ofremaining Area

remaining area

items in the binclass c ≤ 3 (W )class c ≤ 3 (A)

1.00
1.20
1.40
1.60
1.80
1.25
1.45
1.65
1.85
1.50
1.70
1.90
1.75
1.95

> 0.250> 0.361> 0.472> 0.583> 0.694> 0.386> 0.497> 0.608> 0.719> 0.522> 0.633> 0.744> 0.658> 0.769(Ar = 1 − A)
< 0.750< 0.639< 0.528< 0.417< 0.306< 0.614< 0.503< 0.392< 0.281< 0.478< 0.367< 0.256< 0.342< 0.231(Wr = Ar × 1.543)< 1.157< 0.986< 0.815< 0.644< 0.472< 0.948< 0.776< 0.605< 0.434< 0.738< 0.566< 0.395< 0.528< 0.356(W + Wr )< 2.157< 2.186< 2.215< 2.244< 2.272< 2.198< 2.226< 2.255< 2.284< 2.238< 2.266< 2.295< 2.278< 2.306

Table 2: Fourteen possible cases in which we have a
combination of items of class 2 (C2) and 3 (C3) together
with one item x of class 1 (C1) in a single bin B. Here,“sum of weights (W )” and “sum of areas (A)” indicate,respectively, the total weight and area of items of thefirst three classes in B. “Remaining area” is the area
left in the bin that is used for packing items of class 4
or higher. “Weight of items in the remaining area” isan upper bound for the total weight of items of class 4
or higher in B (these items have density no more than
1.543). Finally, “the total weight of items in the bin”
indicate the sum of weights of all items (from all classes)
in B.
the fact that no six items of size larger than 0.3333 can fit
in the same bin [12]. We can conclude that the 14 sub-cases
summarized in Table 2 cover all possibilities for items of thefirst three classes in Case 2.
According to Table 1, the density of items belonging toclass i (4 ≤ i ≤ 12) as well as tiny items is at most 1.543(which is the density of class-4 items). Using a similar argument made for Case 1, we suppose that, after placing acertain number of items of class 2 and 3 beside x in B, ineach sub-case, we are able to completely fill the remaining
empty space of B with the items of the maximum density
1.543. This makes us able to calculate an upper bound forthe maximum total weight of items in B for each of the subcases. The resulting bounds for each sub-case can be foundin the last column of Table 2, where the maximum upperbound among all sub-cases is 2.306, which happens when we
have one item of class 1 in B together with 3 items of class
2 and one item of class 3.
As a result, in both Case 1 and Case 2, the total weightof items in B cannot be more than 2.306.
□

40

ICCG 2022, Sharif UT, February 24, 2022

Preprocessing Imprecise Points for Furthest Distance Queries
Vahideh Keikha∗

Sepehr Moradi†Ali Mohades‡

Abstract
Given is a set of regions in Rd , in the region-based uncertainty model. We show here how to preprocess theseregions so that if one point per region is specified with
precise coordinates, in the query phase, the diameterof the query points can be computed faster than thescratch. We discuss a (1 + ϵ)-approximation algorithmwith running time O( ϵnd ) for answering such queries,
for a set of pairwise disjoint unit balls, after spendingO(n log n + ϵnd ) time for preprocessing.
1

(a)

(b)

Figure 1: Problem definition: (a) A set D of 6 imprecise
points modeled as unit balls, (b) and the diameter of two
different realizations of D.
In this paper, we address the diameter problem in thissetting.

Introduction

It is a common assumption in different areas of computational geometry that the input is a set of points. However, we usually face the problems at which the input
data are not precise due to several resources, namely including bounded precision of measuring devices, rounding errors in calculations, etc. In some cases, we already know in which region each particular point wouldlie, however, the exact locations of the points are still
unknown. One then may assume such a region as animprecise point, that could be a disk, rectangle, line
segment, etc.
In recent years, frequent analysis of uncertain data
has been actively researched in computation modelingof real-world problems. There are numerous exact andapproximation algorithms for processing uncertain data.
Designing an exact algorithm that works for all possible
instances may produce a big data structure and mayneed time-consuming calculations. As a result, thesealgorithms demand much time and space as their inputs are indeed superset compared to the standard algorithm, where the input is a set of points. There havebeen efforts to resolve this problem by careful analysis of
the worst-case or the best-case behavior of the input instances, however, all cases are likely to happen. In someother scenarios, producing the lower and upper boundfor feasible solutions may suffice. Another standpointis preprocessing uncertain data for speeding-up the further computations on precise instances received later.
∗ Institute of Computer Science, Czech Academy of Sciences,
Czech Republic keikha@cs.cas.cz† Department of Computer Science, Amirkabir University ofTechnology semolation@gmail.com‡ Department of Computer Science, Amirkabir University ofTechnology mohades@aut.ac.ir

41

Problem 1 (Diameter Query) LetD={d1 , . . . , dn } be a set of balls in Rd . For a given
query point set Q = {p1 , . . . , pn }, where pi ∈ di , ourobjective is to find the diameter of Q in o(dn2 ) time,after preprocessing. We call the set Q a realization of
D; see Figure 1.
Related work. The region-based model of imprecision was introduced and extensively studied by Löffler
and van Kreveld. Several models are already established
for processing a set of imprecise points for (possibly)
speeding up the sorting problem [17], computing an arbitrary triangulation [9, 18], the Delaunay triangulation [2, 11], and the convex hull of a query set in R2 [4].
In particular, it is previously shown that for a set of imprecise points modeled as convex polygons, with totallyO(n) vertices, an arbitrary triangulation of a query set
with one point in each region can be computed in O(n)time after spending O(n log n) for the preprocessing [18].
The same problem was also studied in [11] at which thesame results also hold for computing a Delaunay triangulation. See also [2, 9]. For a set of imprecise points inthe plane modeled as lines, it is shown that the preprocessing does not speed up the closest pair computation,
the Delaunay triangulation, and the sorting problem on
the realizations received later [4], where they lie on givenlines known in advance. However, in the same paper, it
is shown that preprocessing a set of lines, can speed up
computing the convex hull of the points (on those lines)
received later.
The diameter of a set of points is the maximum pairwise distance between the points in the set. Computing the diameter of a set of points has a long history.
It is shown that computing the diameter in Rd needs5th Iranian Conference on Computational GeometryΩ(n log n) time in any algebraic decision tree, by a reduction from the set disjointedness problem. But thebest-known algorithm for computing the diameter in Rd
takes O(min{nd log n, n2 logs−2 n, n2 ds−2 }) time, wheres ≈ 2.376 [5, 13]. However, this running time can be improved for specific values of d > 2 [5]. For d = 2, nearlinear approximation algorithm exists for the diameter
problem [8]. We refer the reader to [5, 12] for a complete
list of algorithms for the diameter problem in different
dimensions. We note that the diameter problem has extensively used as a black box in database queries. See,e.g., [6].
Contribution. We show there exists a (1 + ϵ)approximation for approximating the diameter queries
on pairwise disjoint unit disks, that takes O( ϵnd ) time,after spending O(n log n + ϵnd ) time for preprocessing(Sec 3.2).
2

Preliminaries

For a set Q of points in Rd , let diam(S) denote thediameter of Q. In the following, we recall the definitions
we use from the literature.
Let G = (S, E) be a geometric graph on Q. Let
dG (p, q) denote the geodesic distance between any pairp, q ∈ Q, that is defined as the length of the shortest
path between these two points in G. The graph G iscalled a t-spanner for some t ≥ 1, if for any two points
p, q ∈ Q we have dG (p, q) ≤ t|pq|, where |pq| is the Euclidiean distance between p and q. The parameter t isrefereed to as the stretch factor.
2.1

Well Separated Pair Decomposition (WSPD)Let Q be a set of points in Rd . Two sets Pi , Qi ⊆ Q
of points are s-well separated if they can be enclosed
within balls of radius r such that the closest distance
between these balls is at least sr. An s-well separated pair decomposition (s-WSPD) of size m for apoint set Q is a set of s-well-separated pairs of subsets {(P1 , Q1 ), . . . , (Pm , Qm )}, where each (Pi , Qi ) ⊂2Q ×2Q , and for any pair of points p, q ∈ Q (p ̸= q) there
is a unique index i for which p ∈ Pi , q ∈ Qi . See Figure 2. Moreover, for any s-well separated pair (Pi , Qi ),for a sufficiently large separation parameter s, we haveapproximately equal distances between any two points,
where one lies in Pi and the other lies in Qi . Furthermore, each pair Pi , Qi has two representatives pi ∈ Pi
and qi ∈ Qi , where pi , qi gives an approximation for
distances between any two points from Pi to Qi . It has
been shown that an s-WSPD of O(sd n) pairs can becomputed in O(n log n + sd n) [3].
We start stating our results with a related question:
Given is a set D of imprecise points modeled by disjoint unit balls. The question is determining whether
there exists an spanner G for an arbitrary realization Q

Pi

p

q

(a)

Qi
(b)

Figure 2: (a) Illustration of a point set and (b) a wellseparated pair decomposition of it with 4 pairs (computed from the quadtree [14]).
of D such that for any other realization Q′ of D whereQ′ ̸= Q, the graph G remains an spanner for Q′ with thesame stretch factor. Abam et al. in [1] answered thisquestion positively by introducing a method for computing the WSPD with respect to a separation ratio s′on the center of the balls. They proved that the computed WSPD remains valid for any realization Q of D,
where the separation ratio s of the WSPD on instances′
is calculated according to s = s 2−2 . Then they create aspanner that is valid for any realization.
Let D be a set of n unit balls, and let s′ be the separation ratio, for which one make a WSPD on the centers.
The following result exist:
Lemma 1 (Lemma 1 [1]) Let D be a set of disjoint
unit balls, and let {(Pi , Qi )|1 ≤ i ≤ m} be a WSPD forthe set {c1 , . . . , cn } as the centers of the balls in D, withrespect to s′ = 2s + 2. Let Q = {p1 , . . . , pn } be a set ofpoints, where pj ∈ Dj , for 1 ≤ j ≤ n. For 1 ≤ i ≤ m,
let Pi′ = {pj |cj ∈ Pi } and Q′i = {pj |cj ∈ Qi }. Then{(Pi′ , Q′i )|1 ≤ i ≤ m} is a WSPD for Q with respect tos.
2.2

Point Set Diameter Approximation

A (1 + ϵ)-approximation algorithm already exists forapproximating the diameter of a point set in Rd using WSPD [7] (Chapter 3, Lemma 3.14). Let Q be a
set of n points in Rd . For a given 0 ≤ ϵ ≤ 1, theobjective is computing a pair pu , pv ∈ Q such thatdiam(Q)≤ ∥pu pv ∥ ≤ diam(Q). In the following, we
1+ϵ
recall the algorithm.
Algorithm: Approximating the Diameter [7].
We first compute an s-WSPD for a point set Q, wheres = 4/ϵ. For each WSPD pair (Pi , Qi ), associate a pairof points as representative points pu ∈ Pi , pv ∈ Qi andcompute the distance between them. See Figure 3. We
then remember the maximum distance among all representative points and return it in the end. This would
give a (1 + ϵ)-approximation for the diameter of Q [7].
It is shown that the running time of this algorithm isO(n log n + sd n) as the WSPD needs to be computed.
Although, the number of candidate pairs realizing thediameter is only O(sd n).
42

ICCG 2022, Sharif UT, February 24, 2022

√

y
2r
pv
≥ sr

2r
x

pu

Figure 3: Diameter approximation using WSPD. The
points x, y determine the diameter, and pu , pv approximate the diameter within a factor 1 + ϵ.
Our method is in fact a combination of Abam et al. [1]technique in the preprocessing phase for computing apersistent WSPD which is computed on the disk centers, and the diameter approximation algorithm [7] inthe query phase, using the computed WSPD in the preprocessing step.
3

Computing the Diameter after Preprocessing

Observe that for any set D of n imprecise points in R2 ,there is no preprocessing with running time o(n log n)
on D to speed-up answering the diameter queries on D
to o(n log n) time. That is because all such problems
simulate the point set case, and it is known that there
is a lower bound Ω(n log n) for the diameter problem in
any algebraic decision tree [12]. In other words, if the
preprocessing takes o(n log n) time, this would result inan o(n log n) time algorithm for the diameter of a setof points in the plane. As another variant consider the
input regions as a set of parallel lines in the plane. If
the 2D points are sorted in just a single direction, one
cannot compute their diameter in less than Ω(n log n)time [15]. Because, if D is a set of parallel lines, e.g.,along the x-axis, we can only anticipate the x-order ofthe points (received later), from which the lower boundfollows.
For a set of unit disks in R2 , the diameter query problem can be solved in O(n) time after spending O(n log n)time for preprocessing. Let D be a set of unit disks inthe plane. It is known that the Delaunay triangulationof a realization of D, as the query set, can be computedin O(n) time after spending O(n log n) time for preprocessing. Hence, the convex hull can be extracted in O(n)time. Having the convex hull, the diameter also can becomputed in O(n) time, as all the antipodal pairs of aconvex polygon can be computed in O(n) time and thediameter is among them [16].
In Rd , we focus on approximation algorithms. An obvious constant factor approximation algorithm for thisproblem is the smallest enclosing ball (SEB) of a setof points that approximates the diameter of the points
43

within a factor 33 . Consider the configuration at whichfour points on the boundary of the SEB forms an equilateral triangular-based pyramid, and the side length ofeach triangular face determines the diameter. If one
translates any pair of these points on the boundary of
the SEB, to get closer, the diameter
enlarges between√
at least one pair. Hence, a ( 33 + ϵ)-approximation of
the diameter of any set of points in Rd can be computed in O(dnz/ϵO(1) ) time by using the randomized
O(1 + ϵ)-approximation algorithm in [10] for computing
the SEB of a set of points in Rd , at which z is a parameter depending on the input 1 . Next, we discuss a(1 + ϵ)-approximation algorithm.
3.1

Preprocessing

In this section, our objective is to preprocess the regions, such that when the exact position of points are
given, one can compute and return an approximation of
the diameter in o(n log n) time. To solve the problem,in our algorithm we use the aforementioned techniquethat returns a (1 + ϵ)-approximation of diameter using WSPD on the point set in O(n/ϵ2 ). However, weneed to compute the WSPD on the point set according to a specific separation factor s = 4ϵ , but it takesO(n log n + s2 n) time and makes the algorithm useless.
Therefore, in the case where the input is a set of disks,
we use Abam et al. [1] technique for computing a WSPD
on the center points of the disks with the separation parameter s′ = 2s + 2, which has been proved that would
be valid for any realization according to separation factor s. Hence, we do not need to compute the WSPD oneach instance, and the WSPD is computed only once inthe preprocessing phase.
Lemma 2 Let {(Ai , Bi )|1 ≤ i ≤ m} be a WSPD on
the set {c1 , . . . , cn } of given disjoint unit disks with respect to s′ = 8ϵ + 2. Let Q = {p1 , . . . , pn } be a set ofpoints, where pj ∈ Dj , for 1 ≤ j ≤ n. For 1 ≤ i ≤ m,
let A′i = {pj |cj ∈ Ai } and Bi′ = {pj |cj ∈ Bi }. Then{(A′i , Bi′ )|1 ≤ i ≤ m} is a WSPD for Q with respect tos = 4ϵ .
Proof. According to Lemma 1 the {(A′i , Bi′ )|1 ≤ i ≤m} would be a valid WSPD for any instance with re′spect to separate factor s = s 2−2 . We assumed the separate factor of the WSPD on the center points is s′ =8
( 8ϵ +2)−28s′ −2= 2ϵ = 4ϵ .
□ϵ + 2, so we have: s = 2 =2
3.2

Query Phase

Now, when we are given a realization of the balls, wewish to compute a (1+ϵ)-approximation of the diameterin O(n/ϵd ) time. It follows from Lemma 2 that we can
1 We note this is the best-known algorithm for computing theSEB, that has a linear dependency on d.

5th Iranian Conference on Computational Geometry

do this by having a WSPD on the center points withrespect to separation factor s = 4ϵ . In addition, our
WSPD is valid for any other realization.

[4] E. Ezra and W. Mulzer. Convex hull of points lying on lines in o(n log n) time after preprocessing.
Comput. Geom., 46(4):417–434, 2013.

Theorem 3 For any given set D = {D1 , . . . , Dn } of n
imprecise points modeled as the same size balls which
are pairwise disjoint, a (1 + ϵ)-approximation of the diameter of a realization Q of D can be computed in O( ϵnd )time, after O(n log n + ϵnd ) preprocessing time.

[5] D. V. Finocchiaro and M. Pellegrini. On computing the diameter of a point set in high dimensional
euclidean space. Theoretical Computer Science,
287(2):501–514, 2002.

Proof. Let s = 4ϵ and s′ = 2s + 2 = 8ϵ + 2 andQ = {p1 , . . . , pn } be the set of precise points. Let{(Ai , Bi )}i=1,...,m be an s′ -WSPD for the center points,
of size m = O(s′2 n), and let A′i = {pj |cj ∈ Ai },Bi′ = {pj |cj ∈ Bi }. It follows from Lemma 1 that{(A′i , Bi′ )|1 ≤ i ≤ m} is a WSPD for Q with respect
to separation parameter s = 4ϵ .
Then, we associate one point to each set as the representative point, let pa ∈ A′i and pb ∈ Bi′ be the representative points of the sets A′i and Bi′ respectively. Fromthe presented approximation algorithm for the diameterin [7], by calculating the distance between representative points of each pair and computing the maximum
distance among all, we have a (1 + ϵ)-approximation of
the diameter of any realization in O(s′d n) time.
□4

Discussion

The main open question is finding an algorithm forthe general version, as our approach cannot be extended to overlapping disks or disks of arbitrary size.
We note that since the WSPD gives the nearest neighbour pairs in a set of points, our results give also an
O(1)-approximation algorithm for the nearest neighbour query for a realization of D in high dimensions.
Acknowledgement The authors would like to thankan anonymous reviewer for pointing out the efficient exact algorithm for the 2-d case. V.K is Supported by the
Czech Science Foundation, grant number GJ19-06792Y,
and by institutional support RVO: 67985807.
References[1] M. A. Abam, P. Carmi, M. Farshi, and M. Smid.
On the power of the semi-separated pair decomposition. Comput. Geom., 46(6):631–639, 2013.
[2] K. Buchin, M. Löffler, P. Morin, and W. Mulzer.
Delaunay triangulation of imprecise points simplified and extended. In WADS, pages 131–143.
Springer, 2009.
[3] P. B. Callahan and S. R. Kosaraju. A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential
fields. J. ACM, 42(1):67–90, 1995.

[6] X. Guo, X. Yang, D. Chen, and C. Chen. Diameteraware extreme group queries.
IEEE Access,
6:58687–58701, 2018.
[7] S. Har-Peled. Geometric approximation algorithms.
Number 173. American Mathematical Soc., 2011.
[8] J. Hong, Z. Wang, and W. Niu. A simple approximation algorithm for the diameter of a set of points
in an euclidean plane. Plos one, 14(2):e0211201,
2019.
[9] V. Keikha, A. Mohades, and M. D. Monfared. On
the triangulation of non-fat imprecise points. In
CCCG, pages 114–121, 2016.
[10] A. Krivošija. Probabilistic smallest enclosing ball inhigh dimensions. Technical report for Collaborative
Research Center SFB 876 Providing Information
by Resource-Constrained Data Analysis, page 13,
2019.
[11] M. Löffler and J. Snoeyink. Delaunay triangulationof imprecise points in linear time after preprocessing. Comput. Geom., 43(3):234–242, 2010.
[12] G. Malandain and J.-D. Boissonnat. Computing
the diameter of a point set. Internat. J. Comput.
Geom. Appl., 12(06):489–509, 2002.
[13] F. P. Preparata and M. I. Shamos. Computational Geometry: an Introduction. pages 95–149.
Springer, 1985.
[14] H. Samet. The quadtree and related hierarchical data structures. ACM Computing Surveys(CSUR), 16(2):187–260, 1984.
[15] R. Seidel. A method for proving lower bounds
for certain geometric problems. In Machine Intelligence and Pattern Recognition, volume 2, pages
319–334. Elsevier, 1985.
[16] M. I. Shamos.
Thesis. 1978.

Computational geometry. Ph.D.

[17] I. van der Hoog, I. Kostitsyna, M. Löffler, andB. Speckmann. Preprocessing ambiguous imprecise
points. arXiv preprint arXiv:1903.08280, 2019.
[18] M. Van Kreveld, M. Löffler, and J. S. Mitchell. Preprocessing imprecise points and splitting triangulations. SIAM J. Comput., 39(7):2990–3000, 2010.
44

ICCG 2022, Tehran, February 24, 2022

The final problem I worked on with Saeed Mehrabi∗
Prosenjit Bose†

The last problem that I worked on with Saeed was a problem called the “Boundary Labeling problem”. The
essence of the problem is the following: Given a set of objects inside a rectangle, we wish to label these objects where
the labels are located outside the rectangle. The goal is to draw a curve from each object inside of the rectangle
to the label outside the rectangle. There are many variants of the problem, such as restricting which sides of therectangle the curve is allowed to intersect, forbidding curves from intersecting or restricting the type of curve thatis allowed. There are also some optimization questions such as whether one can minimize the total length of thecurves. I will review the results that Saeed and I and our co-authors obtained for this family of problems.

∗ In memory of Saeed Mehrabi, former PC of ICCG, who passed away unexcpectedly.

† School of Computer Science, Carleton University, Ottawa, Canada, jit@scs.carleton.ca

45

46

Index of Authors

Abam, Mohammad Ali, 1Keikha, Vahideh, 41

Ashok, Pradeesha, 7

Krohn, Erik, 19

Bahrami, Mohammad Reza, 1

Mohades, Ali, 41

Bakhshesh, Davood, 11Moradi, Sepehr, 41

Bose, Prosenjit, 45
Nikbakht, Pooya, 27, 35
Farshi, Mohammad, 11
Hillberg, Hannah Miller, 19

Pahlow, Alex, 19

Jabbarzade Ganje, Peyman, 1

Sajadpour, Arezoo, 27

Kamali, Shahin, 27, 35

V P, Abidha, 7