Covering Simple Orthogonal Polygons with Rectangles

Basu Roy, Aniket

doi:10.4230/LIPIcs.APPROX/RANDOM.2025.2

Covering Simple Orthogonal Polygons with Rectangles

Aniket Basu Roy

Department of Computer Science and Information Sciences, Birla Institute of Technology and Science, Pilani, K K Birla Goa Campus, Zuarinagar, Sancoale, Goa, India

Abstract

We study the problem of Covering Orthogonal Polygons with Rectangles, focusing on three variants: covering the interior, the boundary, and the corners. While previous work provided constant-factor approximation algorithms for these problems, significant improvements had not been achieved for over two decades. The main contribution of this work is the development of a Polynomial Time Approximation Scheme (PTAS) for both the Boundary Cover and Corner Cover problems on simple polygons, using a local search algorithm. Our work advances the state of the art, improving upon the previous best-known $4$ -approximation for the Boundary Cover and $2$ -approximation for the Corner Cover problems.

The technical core of our work lies in proving the existence of planar support graphs for certain geometric hypergraphs defined by the polygon and its containment-maximal rectangles. This structural insight enables the application of the local search framework to achieve the PTAS results. We also demonstrate the limitations of this approach by constructing instances where local search fails for the Interior Cover and certain dual problems, such as the Maximum Antirectangle and Hitting Set problems. Additionally, the methods yield a PTAS for a special case of the Discrete Independent Set problem for rectangles. These results not only settle longstanding open questions but also introduce new techniques that may be of independent interest within computational geometry.

Keywords and phrases:

Polygon Covering, Approximation Algorithms, Orthogonal Polygons, Rectangles, Local Search, Planar Supports

Category:

APPROX

Funding:

Aniket Basu Roy: BITS Pilani NFSG ref. N5/25/1052

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Computational geometry

Related Version:

Extended Version: https://arxiv.org/abs/2406.16209 [45]

Acknowledgements:

The author is thankful to the Theory group at Aarhus, particularly to Peyman Afshani and Chris Schwiegelshohn. Also, thanks to Sourav Chakraborty and Abhiruk Lahiri for their valuable feedback, which improved the presentation of the paper. Lastly, the author would like to thank Nguyễn Kim Thắng for insightful discussions on the Interior Cover problem during the pandemic days.

DOI:

10.4230/LIPIcs.APPROX/RANDOM.2025.2

Event:

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Editors:

Alina Ene and Eshan Chattopadhyay

Series and Publisher:

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

1 Introduction

Covering orthogonal polygons with the minimum number of rectangles is a fundamental problem in computational geometry, with direct applications in image compression [37], satellite image mosaic selection [46], and access control lists in network routers [4]. Given a polygon whose sides are all axis-aligned, the goal is to cover it exactly with the smallest set of axis-parallel rectangles. This problem, also known as the rectilinear picture compression problem, has been known to be NP-hard for decades, even for polygons without holes [23].

The best-known polynomial time approximation algorithm independent of the number of holes in the polygon has an approximation ratio of $O(\sqrt{\log n})$ due to Kumar and Ramesh [39]. Franzblau gave a $(2+h)$ -approximation algorithm which implies a $2$ -factor approximation for simple polygons [27], where $h$ is the number of holes.

Variants of the problem have also been studied. The Boundary Cover problem asks for the minimum number of rectangles to cover the boundary of the polygon, while the Corner Cover problem focuses on covering just the corners. In 1981, Chaiken, Kleitman, Saks, and Shearer [15] studied their respective duality gaps, whereas Culberson and Reckhow [23] proved that even the boundary cover problem is NP-hard for hole-free polygons. Furthermore, the problem was proved to be $\mathrm{APX}$ -hard when we allow holes in the polygon for the interior cover as well as the boundary cover problem by Berman and DasGupta [11].

Although several articles have been published over the years, especially from the perspective of applications [46, 37] and experiments [31, 34], researchers have failed to make any theoretical improvements for the last two decades.

In this work, we settle the status of the Boundary Cover problem by showing a Polynomial Time Approximation Scheme (PTAS) using Local Search for simple orthogonal polygons. To our knowledge, the best-known approximation factor is $4$ since 1997 [11]. See Table 1 for an overview of the known results and our contributions.

Table 1: State of the art for the studied variants of the Polygon Covering problem, where our results are highlighted in bold.

	Without holes	Possibly with holes
Corner	$2$ -apx [11], PTAS	NP-h [11], $4$ -apx [11]
Boundary	NP-h [23], PTAS	NP-h [22], $4$ -apx [11], $\mathrm{APX}$ -h [11]
Interior	NP-h [23], $2$ -apx [27]	NP-h [28], $O(\sqrt{\log n})$ -apx [39], $\mathrm{APX}$ -h [11]

1.1 Our Contribution

We prove that Local Search yields a PTAS for the Boundary Cover problem on simple orthogonal polygons, improving the previous best-known $4$ -approximation [11]. We show that the same Local Search approach also gives a PTAS for the Corner Cover problem on simple polygons, surpassing the earlier $2$ -approximation [11]. Our main technical advance is to show that, for any simple orthogonal polygon, the hypergraph defined by its containment-maximal rectangles and boundary points admits a planar support graph. This structural property is the key to enabling the PTAS results. As a by-product, we obtain a PTAS for a special case of the Discrete Independent Set problem for rectangles, where the rectangles are containment-maximal with respect to a fixed simple orthogonal polygon and the point set lies on the boundary. We also establish the limitations of this Local Search framework: for the Interior Cover problem and for dual problems like Maximum Antirectangle and Hitting Set (with points restricted to the boundary), we construct instances where the Local Search solution size can be arbitrarily far from that of the optimal solution.

In the following, we define a few terms and state our results. Given a simple orthogonal polygon $P$ and a family of containment-maximal rectangles ${\mathcal{R}}$ contained in $P$ , for every point $p\in\partial P$ we define a hyperedge ${\mathcal{R}}_{p}:=\{R\in{\mathcal{R}}\mid p\in R\}$ . Thus we define a hypergraph $({\mathcal{R}},\{{\mathcal{R}}_{p}\}_{p\in\partial P})$ where the vertex set is ${\mathcal{R}}$ and the hyperedges are ${\mathcal{R}}_{p}$ for every $p\in\partial P$ . For the sake of brevity, we shall denote $({\mathcal{R}},\{{\mathcal{R}}_{p}\}_{p\in\partial P})$ as $({\mathcal{R}},\partial P)$ . We denote its dual hypergraph by $(\partial P,{\mathcal{R}})$ . Clearly, the Boundary Cover problem is the Set Cover problem on the class of hypergraphs $({\mathcal{R}},\partial P)$ , i.e., covering $\partial P$ with a minimum sized subset of ${\mathcal{R}}$ .

Below we state our result on the Boundary Cover problem which improves upon the $4$ -approximation algorithm by Berman and DasGupta [11].

Theorem 1.

Local Search yields a PTAS for the Boundary Cover problem for simple orthogonal polygons.

The same Local Search algorithm yields a PTAS for the Corner Cover problem improving upon their $2$ -approximation algorithm for simple polygons [11]. However, it is not known whether the Corner Cover problem is NP-hard when the polygons are simple.

Theorem 2.

Local Search yields a PTAS for the Corner Cover problem for simple orthogonal polygons.

The Maximum Independent Set of Rectangles problem has garnered a lot of attention in the past $25$ years [3, 16]. In the recent past, Mitchell made a breakthrough [40] by proving a $10$ -approximation algorithm which was subsequently improved to $2+\epsilon$ by Gálvez, Khan, Mari, Mömke, Reddy, and Wiese [30]. There is a QPTAS known due to Adamaszek and Wiese [2], and the open question is to find a PTAS. The discrete version of the problem, the Maximum Discrete Independent Set of Rectangles (MDISR) has also been studied where apart from the family of rectangles there is also a point set as part of the input. Here two rectangles are said to have a discrete intersection if their (continuous) intersection also contains an input point. For this problem, the only known result is an $O(\log n)$ -approximation algorithm by Ene, Har-Peled, and Raichel [26]. A PTAS is known via Local Search for this discrete version if we replace rectangles with non-piercing regions¹¹1A family of geometric objects is called non-piercing if for every pair of intersecting objects $A$ and $B$ , both $A\setminus B$ and $B\setminus A$ are simply connected regions. Observe that rectangles are piercing regions. [10].

The Maximum Independent Set problem on the hypergraph $({\mathcal{R}},\partial P)$ translates to a special class of the MDISR problem where the rectangles are containment-maximal rectangles with respect to some fixed input simple orthogonal polygon $P$ and the input point set is a subset of the boundary of $P$ .

Theorem 3.

Local Search yields a PTAS for the Maximum Independent Set problem on the geometric hypergraph $({\mathcal{R}},\partial P)$ .

In order to show the PTAS, our main technical contribution is to show the existence of planar support for the above hypergraphs defined on the boundary cover problem instance as stated below. Informally, given a hypergraph $H=(V,{\mathcal{F}})$ , we say $G=(V,E)$ is a support graph of $H$ if for every hyperedge $F\in{\mathcal{F}}$ , the induced subgraph $G[F]$ is connected. In addition, if $G$ is planar we call it a planar support. See Definition 9 for a formal definition.

Theorem 4 (Planar Support for Boundary Cover).

Given a simple orthogonal polygon $P$ and a set of containment-maximal rectangles ${\mathcal{R}}$ with respect to $P$ , there exists a planar support graph for $({\mathcal{R}},\partial P)$ .

In order to prove this theorem, we observe many novel properties of containment-maximal rectangles, which could be of independent interest and useful elsewhere. As a corollary of this theorem, it immediately follows that Local Search yields a PTAS for the boundary cover problem and the corner cover problem by applying a result by Mustafa and Ray [41]. Similarly, Theorem 4 also implies Theorem 3 from a result by Chan and Har-Peled [20]. These Local Search results by Chan and Har-Peled [20], and Mustafa and Ray [41] were independently devised and constitute the above-mentioned Local Search framework. Please refer to Subsection 2.1 for more on this framework. For the rest of this article, the reader may alternatively consider the framework as a black box, and focus on the proof of Theorem 4.

On the negative side, we construct interior cover problem instances whose minimal support graphs contain arbitrarily large bicliques, thus implying that a PTAS cannot be attained using the above Local Search framework.

Theorem 5.

For every $r\geq 3$ , there exists simple orthogonal polygon $P$ and an interior cover ${\mathcal{R}}$ such that every arbitrary support graph of $({\mathcal{R}},P)$ contains $K_{r,r}$ .

The Maximum Antirectangle problem restricted to the boundary of the polygon is the same as the Maximum Independent Set problem for the dual hypergraph $(\partial P,{\mathcal{R}})$ , i.e., find a maximum sized subset $P^{\prime}\subset\partial P$ such that for every $R\in{\mathcal{R}}$ , $|R\cap P^{\prime}|\leq 1$ . We give a negative result for this problem (also known as the maximum hidden set problem) by showing the existence of instances such that the dual intersection graphs have arbitrarily large bicliques, thus implying Local Search solution can be arbitrarily smaller than the optimum solution.

Theorem 6.

There exist simple polygons for which the local optimum solution size can be arbitrarily smaller than that of the global optimum solution for the Maximum Antirectangle problem.

To the best of our knowledge, this problem has only been studied in the context of obtaining duality gaps. However, for the more general problem when the point set and the family of rectangles can be arbitrary, there is an $O(n^{0.368})$ -approximation algorithm known due to Chan [17].

The exact same construction as above also implies the same for the Hitting Set problem for the hypergraph $(\partial P,{\mathcal{R}})$ .

Theorem 7.

There exist simple polygons for which the local optimum solution size can be arbitrarily larger than that of the global optimum solution for the Minimum Hitting Set problem for $(\partial P,{\mathcal{R}})$ .

Again we are unaware of any Hitting Set result for this restricted hypergraph. However, for general rectangle hypergraphs the problem enjoys an $O(\log\log OPT)$ -approximation algorithm via $\epsilon$ -nets [5]. There are also matching lower bounds on the size of $\epsilon$ -nets due to Pach and Tardos [42] which implies one cannot hope to improve the approximation factor using $\epsilon$ -nets or by using the natural set cover LP relaxation [12]. The problem is also known to be $\mathrm{APX}$ -hard due to Chan and Grant [18] even when the boundary of every pair of rectangles intersects $0$ or $4$ times.

Please refer to Section 2 for the precise definitions of the above problems.

1.1.1 Technical Overview and Organization

There are broadly two parts to our proof of the existence of the planar supports for hypergraphs defined on the boundary cover instances. If we think of the existence of planar supports as the desired property then we prove that this property is hereditary, i.e., for a fixed simple orthogonal polygon $P$ , if a family of rectangles satisfies the property then so does any of its sub-families (Lemma 31 in Section 4). We also prove that the complete families of containment-maximal rectangles have this property (Lemma 33 in Section 5). By complete we mean the set of all possible containment-maximal rectangles with respect to $P$ .

The central idea in proving the hereditary property is that if a family has a star graph as its support then the family without the rectangle corresponding to the center of the star, still has a planar support. See Figure 1 for an example and Section 3 for the technical details.

We prove the planar support property for complete family of rectangles by induction on some appropriate complexity of the polygon. Given an orthogonal polygon $P$ , we prove that if the statement is true for a complete family with respect to a smaller polygon, then it is also true for the complete family with respect to $P$ . The formal statement can be found in Section 5.

Figure 1: On the left, the boundary of polygon

P

is drawn with thick red lines on an integer grid.

{\mathcal{R}}=\{A,B,C,D,P,Q,R,S\}

where

A=[1,4]\times[1,11]

,

B=[3,6]\times[0,10]

,

C=[5,8]\times[1,11]

,

D=[7,10]\times[0,10]

,

P=[0,10]\times[7,10]

,

Q=[1,11]\times[5,8]

,

R=[0,10]\times[3,6]

,

S=[1,11]\times[1,4]

. A support graph for the boundary cover instance

{\mathcal{R}}

with respect to

P

is drawn on the right. Let

R_{c}=[1,10]\times[1,10]

. The minimal support graph for the boundary cover instance

{\mathcal{R}}\cup\{R_{c}\}

is a star graph with

R_{c}

as the center of the star.

1.2 Related Work

Given an orthogonal polygon $P$ , define a graph $G=(V,E)$ where $V$ is a finite point set in $P$ , and $(p,q)\in E(G)$ if there exists an axis-parallel rectangle $R\subseteq P$ such that $p,q\in R$ . Observe that a polygon covering corresponds to a clique cover in $G$ if $V$ is sufficiently dense in $P$ ²²2E.g., extend all the sides of $P$ to form a grid. Define $V$ to be all the grid points that are in $P$ .. A natural lower bound is the size of an independent set in $G$ , which is also called an antirectangle. The minimum clique cover size is denoted by $\theta$ and the maximum antirectangle (independent set) size is denoted by $\alpha$ . As mentioned by Chaiken et al. [15], Chvátal asked whether $\theta\stackrel{{\scriptstyle?}}{{=}}\alpha$ , which was disproved by Szemerédi by constructing a polygon with $\theta=8$ and $\alpha=7$ . Chung managed to attain the same bound using a simple polygon. Erdős asked whether there exists a constant $c>1$ such that $\theta\leq c\cdot\alpha$ . The only known upper bound is $\theta=O(\alpha\log\alpha)$ due to Franzblau [27].

Covering general polygons (not-necessarily orthogonal) by minimum number of convex polygons has also been studied and it is known as the Convex Cover problem and its dual problem is known as the Hidden Set problem. There has been recent progress made by Browne, Kasthurirangan, Mitchell, and Polishchuk [13], where they proved approximation ratios of $6$ and $8$ for the covering and its dual problem, respectively. On the other hand Abrahamsen proved that the Convex Corner problem is $\exists\mathbb{R}$ -complete [1].

Even more generally, Haussler and Welzl proved that any hypergraph with VC-dimension $d$ admits $\epsilon$ -nets of size $O(\frac{d}{\epsilon}\log\frac{d}{\epsilon})$ [33]. Using the multiplicative weight update method by Brönnimann and Goodrich [12], this implies an $O(\log OPT)$ -approximation for the corresponding covering problem. For general rectangle families, there are also matching lower bounds of $O(1/\epsilon\log 1/\epsilon)$ [42]. Also see [19, 21, 47] that studies other measures of complexity of geometric hypergraphs like union complexity and shallow cell complexity which have an effect on the approximation factors of the corresponding covering problem.

Also, the authors in [4] studied the Rectangle Rule List Minimization problem, which is a generalization of the Orthogonal Polygon Covering problem.

2 Preliminaries

All polygons are assumed to be orthogonal, i.e., their sides are parallel to either the vertical or horizontal axes. A polygon is said to be simple if it has no holes, i.e., it is simply connected. Given a simple orthogonal polygon $P$ , we denote $\partial P$ to be the boundary of $P$ . All rectangles are assumed to be axis-parallel. A rectangle $R\subseteq P$ is called containment-maximal with respect to a polygon $P$ if $R$ is not contained in a rectangle $R^{\prime}\subseteq P$ of larger area. Henceforth, we shall use the word “maximal” to denote containment-maximal for the sake of brevity. Observe, as a consequence of maximality, all four sides of $R$ have non-empty intersection with $\partial P$ . We denote ${\mathcal{R}}^{K}(P)$ to be the set of all maximal rectangles with respect to $P$ , also referred as the complete family of rectangles with respect to $P$ .

Definition 8 (Blocker of a Maximal Rectangle).

Given an orthogonal polygon $P$ and a maximal rectangle $R\subseteq P$ , any point $p\in\partial P$ is called a blocker of $R$ if $p\in R$ and $p$ is not a corner of $R$ . If $p$ intersects the top (resp. bottom, left, right) side of $R$ then $p$ is called a top (resp. bottom, left, right) blocker of $R$ .

For the sake of brevity, we shall sometimes call a side $s$ of $P$ to be a blocker of $R$ if $s\cap R\neq\emptyset$ .

Definition 9 (Support graph of a hypergraph).

Given a hypergraph $H=(V,{\mathcal{F}})$ where $V$ is the vertex set and ${\mathcal{F}}\subseteq 2^{V}$ is a family of subsets of $V$ , we say $G=(V,E)$ is a support graph of $H$ if for every $F\in{\mathcal{F}}$ , the subgraph induced on F, $G[F]$ is connected.

See Figure 1 for an example of a family of maximal rectangles ${\mathcal{R}}$ with respect to polygon $P$ on the left, and a planar support graph for the hypergraph $({\mathcal{R}},\partial P)$ to its right. Observe, that the intersection graph of the rectangles is always a valid support graph, which may not be planar.

Interior Cover problem Input: An orthogonal polygon $P$ in the plane. Question: A minimum sized set of rectangles ${\mathcal{R}}$ such that $\bigcup_{R_{i}\in{\mathcal{R}}}R_{i}=P.$

Boundary Cover problem Input: An orthogonal polygon $P$ in the plane. Question: A minimum sized set of rectangles ${\mathcal{R}}$ such that $\partial P\subseteq\bigcup_{\begin{subarray}{c}R_{i}\in{\mathcal{R}}\\ R_{i}\subseteq P\end{subarray}}R_{i}.$

Corner Cover problem Input: An orthogonal polygon $P$ in the plane. Question: A minimum sized set of rectangles ${\mathcal{R}}$ such that $\textsf{corner}P\subseteq\bigcup_{\begin{subarray}{c}R_{i}\in{\mathcal{R}}\\ R_{i}\subseteq P\end{subarray}}R_{i}$ where $\textsf{corner}P$ denotes the set of corners of $P$ .

Maximum Independent Set problem for $({\mathcal{R}},\partial P)$ Input: An orthogonal polygon $P$ in the plane and a set of containment-maximal rectangles ${\mathcal{R}}$ with respect to $P$ . Question: A maximum sized subset of rectangles ${\mathcal{R}}^{\prime}\subseteq{\mathcal{R}}$ such that for every $R_{i},R_{j}\in{\mathcal{R}}^{\prime}$ , there does not exist a point $p\in\partial P$ where $p\in R_{i}\cap R_{j}$ .

Maximum Antirectangle problem Input: An orthogonal polygon $P$ in the plane. Question: A maximum sized set of points $Q\subset P$ such that for every $p,q\in Q$ , there does not exist a rectangle $R\subseteq P$ where $p,q\in R$ .

Minimum Hitting Set problem for $(\partial P,{\mathcal{R}})$ Input: An orthogonal polygon $P$ in the plane and a set of containment-maximal rectangles ${\mathcal{R}}$ with respect to $P$ . Question: A minimum sized point set $P^{\prime}\subset\partial P$ such that for every $R\in{\mathcal{R}}$ , $R\cap P^{\prime}\neq\emptyset$ .

2.1 Local Search Framework

Local search has been a very useful heuristic for decades, and has been proved to give good approximation ratios, particularly for clustering and geometric optimization algorithm [6, 29]. In this work, we will consider the particular Local Search framework introduced by Mustafa and Ray for covering problems in [41]. Almost the same framework works for packing problems, which was introduced around the same time by Chan and Har-Peled in [20]. Over the years, this framework has been used for a variety of packing and covering problems [7, 8, 9, 10, 32, 38, 43, 44]. As a consequence of this framework, it is sufficient to show the existence of a sparse support graph for a hypergraph: in order to prove that Local Search yields a PTAS for the corresponding covering problem. Here by sparse, we mean the graph has strongly sublinear separators, which is a necessary condition for planarity.

The study of planar supports predates the Local Search framework in question. It has been studied in the context of hypergraph drawing. See [14, 35, 36], and Section 2 in [44] for a short survey. Durocher and Fraser [25] were arguably the first to make the connection and use the word “support” in the context of Local Search for covering problems.

Below, we state an abstraction of the result of Mustafa and Ray [41].

Lemma 10.

Given a hypergraph $H=(V,{\mathcal{F}})$ where $V$ is the vertex set and ${\mathcal{F}}\subseteq 2^{V}$ is a family of subsets of $V$ , we want to compute the minimum sized $V^{\prime}\subseteq V$ such that for every $F\in{\mathcal{F}}$ , $V^{\prime}\cap F\neq\emptyset$ . If there exists a planar support of $H$ , then the Local Search algorithm computes a $(1+\epsilon)$ -approximate solution in time $n^{O(1/\epsilon^{2})}$ , for $\epsilon>0$ .

Conversely, we state an abstraction of the result of Chan and Har-Peled [20]. Before that we define the dual intersection graph $G$ of a subset $U\subseteq V$ with respect to hypergraph $H=(V,{\mathcal{F}})$ . The vertex set is $U$ , and for every $v,w\in U$ , $(v,w)\in E(G)$ if there exists $F\in{\mathcal{F}}$ such that $v,w\in F$ .

Lemma 11.

Given a hypergraph $H=(V,{\mathcal{F}})$ where $V$ is the vertex set and ${\mathcal{F}}\subseteq 2^{V}$ is a family of subsets of $V$ , we want to compute the maximum sized $V^{\prime}\subseteq V$ such that for every $F\in{\mathcal{F}}$ , $|V^{\prime}\cap F|\leq 1$ . Let $A\subseteq V$ be an optimum solution and $B\subseteq V$ be the solution returned by the Local Search algorithm. If the dual intersection graph of $A\cup B$ with respect to $H$ is planar, then the Local Search algorithm computes a $(1+\epsilon)$ -approximate solution in time $n^{O(1/\epsilon^{2})}$ , for $\epsilon>0$ .

Lastly, see below for the Local Search algorithm for covering the boundary of the input simple polygon $P$ , where $k$ is the Local Search parameter which is set to $c/\epsilon^{2}$ for some appropriate constant $c$ .

Algorithm 1 Local Search Algorithm to cover the boundary of

P

.

2.2 Intersection Patterns

Given a simple orthogonal polygon $P$ , if two maximal rectangles $R$ and $R^{\prime}$ with respect to $P$ have a non-empty intersection then they intersect in one of the following ways:

1.

Corner Intersection. $R$ has exactly one corner of $R^{\prime}$ in its interior and vice versa.
2.

Piercing Intersection. The two vertical (resp. horizontal) sides of $R$ intersect the two horizontal (resp. vertical) sides of $R^{\prime}$ .

Furthermore, if $R$ and $R^{\prime}$ have a piercing intersection and one of the sides of $R$ is contained in one of the sides of $R^{\prime}$ then we say that the two rectangles are aligned to each other. See Figure 2.

Figure 2: The left pair has a corner intersection. The middle and the right have a piercing intersection; in which the right pair are also aligned to each other.

Definition 12.

Given a simple orthogonal polygon $P$ and a set of maximal rectangles ${\mathcal{R}}$ with respect to $P$ , define a binary relation $({\mathcal{R}},\prec)$ . If for every $R,R^{\prime}\in{\mathcal{R}}$ such that $R$ and $R^{\prime}$ have a piercing intersection and the two vertical sides of $R$ intersect the two horizontal sides of $R^{\prime}$ then we say $R\prec R^{\prime}$ .

Observe that $({\mathcal{R}},\prec)$ is irreflexive, asymmetric, and transitive and hence $\prec$ defines a strict partial order on ${\mathcal{R}}$ . More informally, we say $R\prec R^{\prime}$ if they have a piercing intersection and the width of $R$ is less than that of $R^{\prime}$ .

2.3 Left-Right Coloring

In this section, we recall a few definitions and results from a series of work by de Fraysseix, Ossona de Mendez, and Rosenstiehl [24]. They presented the Left-Right Coloring technique that can be used to test whether a graph is planar. Fix some arbitrary vertex in the graph as the root and traverse in a depth-first way. Thus we get a DFS tree, whose edges are subset of the given graph. Left-Right Coloring is a coloring (partitioning) of the cotree edges (the edges in the graph that are not in the DFS tree) such that if such a coloring is possible then cotree edges can be drawn without crossing each other, thus implying the given graph is planar.

Definition 13 (DFS-orientation).

Given an undirected, connected graph $G=(V,E)$ and a fixed vertex $r\in V$ , its DFS-orientation is a directed graph $G^{\prime}=(V,T\uplus B)$ where $T$ is the set of the tree edges obtained by depth-first traversal of $G$ starting from $r$ , and $B=E\setminus T$ is the set of cotree edges. For every tree edge $(u,v)\in E$ , if $u$ is traversed before $v$ in the depth-first traversal then there is a directed edge $(u,v)$ in $G^{\prime}$ . Conversely, for every cotree edge $(u,v)\in E$ , if $u$ is traversed before $v$ in the depth-first traversal then there is a directed edge $(v,u)$ in $G^{\prime}$ .

Thus, $T$ defines a partial order on $V$ where the root of $T$ is the minimum vertex with respect to this partial order. In the following, terms like high and low are used with respect to the same partial order. Given a tree edge $e=(u,v)$ , return edges of $e$ are the cotree edges $e^{\prime}=(v^{\prime},u^{\prime})$ such that $v^{\prime}$ is a descendant of $v$ or $v=v^{\prime}$ , and $u^{\prime}$ is an ancestor of $u$ that is different from $u$ . Define a mapping $low:E\rightarrow V$ , where for every $e\in E$ , $low(e)$ is the minimum vertex with respect to the partial order that can be reached by a directed path starting with $e$ and containing at most one cotree edge.

Definition 14 (Left-Right Coloring).

Let $G^{\prime}=(V,T\uplus B)$ be a DFS-oriented graph. A bipartition of its cotree edges $B=L\uplus R$ into two classes, referred to as left and right, is called left-right coloring, if for every $v\in V$ and outgoing edges $e_{i}$ and $e_{j}$ from $v$ , the following two conditions are satisfied.

$\blacksquare$

All return edges of $e_{i}$ ending strictly higher than $low(e_{j})$ belong to one class, and
$\blacksquare$

All return edges of $e_{j}$ ending strictly higher than $low(e_{i})$ belong to the other class.

Lemma 15 ([24]).

A finite graph $G$ is planar if and only if there exists a Left-Right coloring of the cotree edges with respect to a depth-first-tree $T$ on $G$ .

3 Family of Rectangles with a Kernel

The main results of this section are Lemmata 18 and 30, which in turn are used to prove Lemma 31 in Section 4. In the following, we define a kernel of a rectangle family. Informally, Lemma 18 says that if a rectangle family has a star graph as its support, then the rectangle corresponding to the center of the star belongs to the kernel. Lemma 30 states that a family of rectangles without its kernel still has a planar support.

Definition 16 (Kernel of a Family).

Given a family of maximal rectangles ${\mathcal{R}}$ with respect to a simple polygon $P$ , the kernel of $({\mathcal{R}},\partial P)$ is defined as follows.

ker({\mathcal{R}}):=\displaystyle\bigcap_{\begin{subarray}{c}p\in\partial P\\ |{\mathcal{R}}_{p}|\geq 2\end{subarray}}{\mathcal{R}}_{p}

where ${\mathcal{R}}_{p}:=\{R\in{\mathcal{R}}\mid p\in R\}$ .

A family $({\mathcal{R}},\partial P)$ with non-empty kernel $ker({\mathcal{R}})$ is called proper if for every $R\in{\mathcal{R}}$ there exists $p\in\partial P$ such that $ker({\mathcal{R}})\cup\{R\}\subseteq{\mathcal{R}}_{p}$ . See Figure 3 for an example of a family that is not proper.

Figure 3:

(\{R_{i},R_{j},R_{k},R_{\ell},R_{c}\},\partial P)

has a non-empty kernel

\{R_{c}\}

but it is not proper. Whereas,

(\{R_{i},R_{j},R_{c}\},\partial P)

is proper and has the same kernel. Note that

\partial P

is drawn with red lines.

Observation 17.

Every proper family $({\mathcal{R}},\partial P)$ with a non-empty kernel has a support that is a star graph with the center vertex corresponding to a kernel rectangle.

In the following, we show that the converse is also true.

Lemma 18.

Given a family of maximal rectangles ${\mathcal{R}}$ with respect to a simple orthogonal polygon $P$ . If there exists a minimal support graph $G$ of $({\mathcal{R}},\partial P)$ such that $G$ is a star graph then the rectangle corresponding to the center of $G$ belongs to $ker({\mathcal{R}})$ and ${\mathcal{R}}$ is proper.

Proof.

Let $R_{c}$ be the center of $G$ . As $G$ is a minimal support graph of $({\mathcal{R}},\partial P)$ , for every $p\in\partial P$ such that $|{\mathcal{R}}_{p}|\geq 2$ , $R_{c}\in{\mathcal{R}}_{p}$ . If there exists $p\in\partial P$ such that $|{\mathcal{R}}_{p}|\geq 2$ and $R_{c}\notin{\mathcal{R}}_{p}$ then $p$ is not supported by $G$ and hence a contradiction. This implies $R_{c}\in ker({\mathcal{R}})$ .

${\mathcal{R}}$ is proper because otherwise there are isolated vertices in a minimal support. $\hfill\blacktriangleleft$

Throughout this section we assume ${\mathcal{R}}$ to be proper and have a non-empty kernel. Without loss of generality, we consider ${\mathcal{R}}$ to have a unique kernel rectangle, i.e., $ker({\mathcal{R}})=\{R_{c}\}$ . From Definition 12, we can partition the family without its kernel rectangle $R_{c}$ into the following subsets. The set of rectangles that have a corner intersection with $R_{c}$ that we denote by ${\mathcal{R}}_{N}$ . The remaining rectangles in ${\mathcal{R}}$ have a piercing intersection with $R_{c}$ . Among the ones having a piercing intersection, we call the rectangles $R\in{\mathcal{R}}$ to be vertical rectangles if $R\prec R_{c}$ , i.e., ${\mathcal{R}}_{V}:=\{R\in{\mathcal{R}}\mid R\prec R_{c}\}$ . Likewise, we call the rectangles $R\in{\mathcal{R}}$ to be horizontal rectangles if $R_{c}\prec R$ , i.e., ${\mathcal{R}}_{H}:=\{R\in{\mathcal{R}}\mid R_{c}\prec R\}$ . Thus, ${\mathcal{R}}:={\mathcal{R}}_{N}\uplus{\mathcal{R}}_{V}\uplus{\mathcal{R}}_{H}% \uplus\{R_{c}\}$ .

Figure 4: Let

{\mathcal{R}}

be a proper family with

R_{c}

as the kernel rectangle. The above figure shows parts of

\partial P

in bold red. Corner intersection

N\cap R_{c}\cap\partial P=\{p,q\}

. If

R_{j}

belongs to

{\mathcal{R}}

then

p^{\prime}

witnesses the intersection

N\cap R_{j}\cap\partial P

but it is outside

R_{c}

, which implies

R_{c}

is not a kernel. However,

R_{i}

can be part of

{\mathcal{R}}

without contradicting the fact that

R_{c}

is the kernel rectangle.

Lemma 19.

Let $N\in{\mathcal{R}}_{N}$ such that it contains the top-right corner of $R_{c}$ . If there exists $R\in{\mathcal{R}}$ such that $R\cap N\cap\partial P\neq\emptyset$ , then $R$ is either aligned to the top side and/or the right side of $R_{c}$ .

Proof.

Given $N$ , a corner rectangle, there exists two points $p$ and $q$ where $\partial N\cap\partial R_{c}\neq\emptyset$ . See Figure 4. As $N\in{\mathcal{R}}$ and ${\mathcal{R}}$ is proper, at least one or both $p$ and $q$ belongs to $\partial P$ . If there exists $R\in{\mathcal{R}}\setminus\{R_{c}\}$ such that $R\cap N\cap R_{c}\cap\partial P\neq\emptyset$ then either $p$ or $q$ or both are contained in $R$ . Without loss of generality, assume that $p\in R\cap\partial P$ . Then observe that the top side of $R$ is aligned with the top side of $R_{c}$ . The left side of $R$ cannot be aligned with the left side of $N$ , because otherwise there exists a point $p^{\prime}\in\partial P$ such that $p^{\prime}\in(N\cap R\cap\partial P)\setminus R_{c}$ , which implies $R_{c}$ is not a kernel rectangle. See Figure 4. Similarly, if $q\in R\cap\partial P$ then the right side of $R$ is aligned with the right side of $R_{c}$ . $\hfill\blacktriangleleft$

The following observation can be made from Lemma 19.

Observation 20.

For $R_{i},R_{j}\in{\mathcal{R}}_{N}$ , $R_{i}\cap R_{j}\cap\partial P=\emptyset$ .

Lemma 21.

Given a proper family ${\mathcal{R}}$ with kernel rectangle $R_{c}$ , there are at most $2$ corner rectangles, $N_{i}$ and $N_{j}$ containing a fixed corner of $R_{c}$ . Furthermore, $N_{i}$ and $N_{j}$ pierce each other in a non-aligned way.

Proof.

Let $N_{i}$ and $N_{j}$ be two corner rectangles, i.e., $N_{i},N_{j}\in{\mathcal{R}}_{N}$ and they contain the top-right corner of $R_{c}$ . We do a case analysis below and conclude that $N_{i}$ and $N_{j}$ can only have a piercing intersection in a non-aligned way.

1.

Assume $N_{i}$ and $N_{j}$ have a corner intersection between themselves. Without loss of generality, further assume that the left side of $N_{i}$ is to the left of that of $N_{j}$ . There are two subcases. First, the top side of $N_{i}$ is above that of $N_{j}$ . Second, the top side of $N_{i}$ is below that of $N_{j}$ .

In the first subcase, the left side of $N_{j}$ is completely in the interior of $N_{i}$ and $R_{c}$ , which implies that $N_{j}$ is not maximal. Hence, contradiction (see Figure 5, part $a$ ). In the second subcase, $N_{j}\cap R_{c}\cap\partial P=\emptyset$ which implies ${\mathcal{R}}$ is not a proper family, hence a contradiction again (see Figure 5, part $b$ ).
2.

Assume $N_{i}$ and $N_{j}$ have a piercing intersection. The first subcase is that they are aligned to each other and the second subcase is that they are not.

Without loss of generality, assume one of the sides of $N_{j}$ , $s_{j}$ is aligned to $s_{i}$ , the corresponding side of $N_{i}$ and $s_{j}\subset s_{i}$ . As $N_{j}$ is maximal, $s_{j}\cap\partial P\neq\emptyset$ . This also implies that $s_{i}\cap s_{j}\cap\partial P\neq\emptyset$ . Then it contradicts Observation 20 (see Figure 5, part $c$ ).

For an example of $N_{i}$ and $N_{j}$ having a non-aligned piercing intersection, see part $d$ of Figure 5.

Next assume, that there is a third rectangle $N_{k}$ that also contains the top-right corner of $R_{c}$ and $N_{i}\prec N_{k}\prec N_{j}$ . This implies $N_{k}\cap R_{c}\cap\partial P=\emptyset$ , which means ${\mathcal{R}}$ is not proper and hence contradiction (see Figure 5, part $d$ ). $\hfill\blacktriangleleft$

Figure 5: The subfigures are to support the various subcases of the proof of Lemma 21.

\partial P

is drawn in thick red. The fill colors of rectangles

R_{c},N_{i},N_{j},N_{k}

are gray, red, blue, and green, respectively.

As a consequence of Lemma 21, we know that there are at most $8$ corner rectangles in ${\mathcal{R}}$ , at most $2$ per corner of $R_{c}$ . If there is a unique corner rectangle containing the top-right corner of $R_{c}$ , we shall denote it by $N_{\nearrow}$ . If there are two of them then we shall denote them by $N^{v}_{\nearrow}$ and $N^{h}_{\nearrow}$ , where $N^{v}_{\nearrow}\prec N^{h}_{\nearrow}$ . In general, a corner rectangle is denoted by $N^{a}_{b}$ , where $a\in\{v,h,\emptyset\}$ and $b\in\{\swarrow,\nwarrow,\nearrow,\searrow\}$ .

3.1 Vertical and Horizontal Rectangles

We define the subset of maximally vertical rectangles with respect to the partial order $\prec$ as ${\mathcal{R}}^{*}_{V}:=\max\{R\in{\mathcal{R}}_{V}\}$ . Similarly, we define the subset of minimally horizontal rectangles ${\mathcal{R}}^{*}_{H}:=\min\{R\in{\mathcal{R}}_{H}\}$ .

Lemma 22.

There does not exist $3$ rectangles $R_{i},R_{j},R_{k}\in{\mathcal{R}}^{*}_{V}$ (resp. ${\mathcal{R}}^{*}_{H}$ ) such that each one has a corner intersection with the other two in $\partial P$ , i.e., $R_{i}\cap R_{j}\cap\partial P\neq\emptyset$ , $R_{j}\cap R_{k}\cap\partial P\neq\emptyset$ , and $R_{i}\cap R_{k}\cap\partial P\neq\emptyset$ .

Proof.

Assume there exist $3$ rectangles, $R_{i},R_{j},R_{k}\in{\mathcal{R}}$ such that $R_{i}\cap R_{j}\cap\partial P\neq\emptyset$ , $R_{j}\cap R_{k}\cap\partial P\neq\emptyset$ , and $R_{i}\cap R_{k}\cap\partial P\neq\emptyset$ . Combinatorially, triple of rectangles can be have pairwise corner intersection in two ways as shown in Figure 6. If the triple intersect as shown on the left then $R_{i}\cap R_{k}\cap\partial P=\emptyset$ which is a contradiction. If the triple intersect as shown on the right then the bottom side of $R_{j}$ and the right side of $R_{i}$ are completely in the interior of the union of the other two. This implies $R_{i}$ and $R_{j}$ are not maximal which is a contradiction. $\hfill\blacktriangleleft$

Figure 6: Three rectangles can intersect in two ways such that every pair has a corner intersection.

Lemma 22 implies that we can linearly order the rectangles in ${\mathcal{R}}^{*}_{V}$ (resp. ${\mathcal{R}}^{*}_{H}$ ) as shown below.

Definition 23.

Define a linear ordering $<_{v}$ on the rectangles in ${\mathcal{R}}^{*}_{V}$ , such that $R<_{v}R^{\prime}$ if the left side of $R$ is to the left of that of $R^{\prime}$ , for every $R,R^{\prime}\in{\mathcal{R}}^{*}_{V}$ .

Let ${\mathcal{R}}^{*}_{V}=\{V_{1},\dots,V_{k}\}$ , where $V_{1}<_{v}\dots<_{v}V_{k}$ .

Definition 24.

Define a linear ordering $<_{h}$ on the rectangles in ${\mathcal{R}}^{*}_{H}$ , such that $R<_{h}R^{\prime}$ if the bottom side of $R$ is below that of $R^{\prime}$ , for every $R,R^{\prime}\in{\mathcal{R}}^{*}_{H}$ .

Let ${\mathcal{R}}^{*}_{H}=\{H_{1},\dots,H_{\ell}\}$ , where $H_{1}<_{h}\dots<_{h}H_{\ell}$ .

Lemma 25.

Let $R_{i},R_{j}\in{\mathcal{R}}^{*}_{V}$ such that $R_{i}\cap R_{j}\cap\partial P\neq\emptyset$ . There does not exist $R_{k}\in{\mathcal{R}}_{V}$ such that $R_{k}\prec R_{i}$ and $R_{k}\prec R_{j}$ .

Proof.

Without loss of generality, assume $R_{i}<_{v}R_{j}$ . For the sake of contradiction, lets assume such an $R_{k}$ exists. Then $R_{k}$ should be within the left side of $R_{j}$ and the right side of $R_{i}$ in order to have a piercing intersection with them. If $R_{k}$ is aligned to $R_{i}$ then they have an intersection with $\partial P$ outside $R_{c}$ , which means $R_{c}$ is not a kernel rectangle, hence a contradiction (see the left half of Figure 7). Same is the case if it is aligned to $R_{j}$ . If it is aligned to neither $R_{i}$ nor $R_{j}$ , then $R_{k}\cap R_{c}\cap\partial P=\emptyset$ , which means ${\mathcal{R}}$ is not proper, hence a contradiction again (see the right half of Figure 7). $\hfill\blacktriangleleft$

Figure 7: The above subfigures are to support Lemma 25.

Lemma 26.

Let ${\mathcal{R}}^{\prec}_{V}(V_{i}):=\{R\in{\mathcal{R}}_{V}\mid R\prec V_{i}\}$ , for $V_{i}\in{\mathcal{R}}^{*}_{V}$ . There exists a support graph of $({\mathcal{R}}^{\prec}_{V}(V_{i})\cup\{V_{i}\},\partial P)$ that is a star graph with $V_{i}$ as the center.

Proof.

Lemma 25 implies that $V_{i}$ is a kernel rectangle of $({\mathcal{R}}^{\prec}_{V}(V_{i})\cup\{V_{i}\},\partial P)$ . Observation 17 implies that the support graph of $({\mathcal{R}}^{\prec}_{V}(V_{i})\cup\{V_{i}\},\partial P)$ is a star graph with $V_{i}$ as the center. $\hfill\blacktriangleleft$ Same arguments hold for $H_{j}\in{\mathcal{R}}^{*}_{H}$ .

We refer $V_{1},V_{k},H_{1},$ and $H_{\ell}$ to be terminal rectangles.

If $V_{1}$ and $R_{c}$ have a common left blocker, then we call $V_{1}$ to be left-aligned. Likewise, if $V_{k}$ and $R_{c}$ have a common right blocker, then we call $V_{k}$ to be right-aligned. Conversely, if $H_{1}$ and $R_{c}$ have a common top blocker, then we call $H_{1}$ to be top-aligned. Finally, if $H_{\ell}$ and $R_{c}$ have a common bottom blocker, then we call $H_{\ell}$ to be bottom-aligned. Note that a terminal rectangle may or may not be aligned.

3.2 Intersection between Corner and Non-corner Rectangles

From Lemma 19 we know that any vertical or horizontal rectangle having an intersection with $N^{a}_{\nearrow}$ at $\partial P$ , should be top-aligned and/or right-aligned to $R_{c}$ , where $a\in\{v,h,\emptyset\}$ .

Lemma 27.

There are at most $2$ vertical rectangles in ${\mathcal{R}}^{*}_{V}$ and $2$ horizontal rectangles in ${\mathcal{R}}^{*}_{H}$ intersecting a corner rectangle at $\partial P$ . Among these up to $4$ rectangles, there are at most $1$ vertical terminal rectangle, and at most $1$ horizontal terminal rectangle. Furthermore, for a fixed corner of $R_{c}$ , if there are two corner rectangles, then there are at most $1$ vertical and $1$ horizontal rectangle per corner rectangle.

Proof.

Without loss of generality, fix the top-right corner of $R_{c}$ . If there are corner rectangles, then either there is a single corner rectangle or there are two of them.

For the first case, the corner rectangle is $N_{\nearrow}$ and there are possibly $4$ rectangles $V_{i},V_{k}\in{\mathcal{R}}^{*}_{V}$ and $H_{j},H_{\ell}\in{\mathcal{R}}^{*}_{H}$ , where $1\leq i<k$ and $1\leq j<\ell$ such that they intersect $N_{\nearrow}$ at $\partial P$ . Recall that $V_{k}$ and $H_{\ell}$ are terminal rectangles (see Figure 8(a)).

Similar is the case, if there are two corner rectangles, $N^{v}_{\nearrow}$ and $N^{h}_{\nearrow}$ . $N^{v}_{\nearrow}$ has an intersection with $V_{i}$ and $H_{\ell}$ at a boundary point $p$ , whereas, $N^{h}_{\nearrow}$ has an intersection with $V_{k}$ and $H_{j}$ at another boundary point $q$ (see Figure 8(b)). $\hfill\blacktriangleleft$

See Figure 9 for an illustration of all corners having two corner rectangles each, and also Figure 10 for the corresponding support graph.

(a)

N_{\nearrow}

is the unique corner rectangle containing the top-right corner of

R_{c}

. Boundary points

p\in V_{i}\cap H_{\ell}\cap N_{\nearrow}\cap\partial P

and

q\in V_{k}\cap H_{j}\cap N_{\nearrow}\cap\partial P

.

(b)

N^{v}_{\nearrow}

and

N^{h}_{\nearrow}

are the two corner rectangles containing the top-right corner of

R_{c}

. Boundary points

p\in V_{i}\cap H_{\ell}\cap N^{h}_{\nearrow}\cap\partial P

and

q\in V_{k}\cap H_{j}\cap N^{v}_{\nearrow}\cap\partial P

.

Figure 8: The intersection patterns between corner and non-corner rectangles.

We make the following observation.

Lemma 28.

If there are two corner rectangles $N^{v}_{b},N^{h}_{b}$ for a fixed corner $b$ of $R_{c}$ , where $b=\{\nearrow,\nwarrow,\searrow,\swarrow\}$ , then there exists a support graph such that degree of both these corner rectangles in this graph is at most $2$ .

Proof.

Fix $b=\nearrow$ and consider $N_{\nearrow}^{v}$ . From Lemma 27, and Figures 8(b) and 9, we know there exists at most one maximally horizontal rectangle $H_{j}$ , and similarly at most one maximally vertical rectangle $V_{k}$ , such that there is a unique point $p\in N_{\nearrow}^{v}\cap H_{j}\cap V_{k}\cap\partial P\neq\emptyset$ . Recall, from Lemma 26, there exists a support graph such that non-maximally horizontal (resp. vertical) rectangles are adjacent to a unique maximally horizontal (resp. vertical) rectangle. Thus, in a minimal support graph, $N_{\nearrow}^{v}$ has degree at most two. Similar arguments hold for $N_{\nearrow}^{h}$ , and also for other values of $b$ . $\hfill\blacktriangleleft$

$\blacktriangleright$ Remark 29.

For a given corner $b\in\{\nearrow,\nwarrow,\searrow,\swarrow\}$ , we shall ignore all pairs of corner rectangles $N^{v}_{b}$ and $N^{h}_{b}$ , if they exist, from our following graph drawing algorithm. Suppose $v$ is a degree- $2$ vertex, incident to edges $(u,v)$ and $(v,w)$ . Instead of drawing the pair of edges, one can draw an edge $(u,w)$ and place $v$ anywhere in the interior of the drawing of this edge. On the other hand, if $v$ is a degree- $1$ vertex and $(u,v)$ is the only edge incident to it, then this edge can be drawn arbitrarily close to $u$ without intersecting any other edges.

Figure 9: This figure is an extension of Figure 8(b) to all the

4

corners of

R_{c}

. See Figure 10 for the corresponding support graph.

Figure 10: This figure shows the drawing of the support graph of the arrangement shown in Figure 9. The edges drawn in solid lines are to support rectangles intersecting at

p_{i}

,

1\leq i\leq 8

. Whereas the edges that do not involve corner rectangles are drawn in dashed lines.

(a)

(b)

Figure 11: (a) Schema of a planar support graph for

({\mathcal{R}}\setminus ker({\mathcal{R}}),\partial P)

.

{\mathcal{R}}^{*}_{V}=\{V_{1},\dots,V_{7}\}

,

{\mathcal{R}}^{*}_{H}=\{H_{1},\dots,H_{7}\}

,

{\mathcal{R}}_{N}=\{N_{\swarrow},N_{\nwarrow},N_{\nearrow},N_{\searrow}\}

. For every

V_{i}\in{\mathcal{R}}^{*}_{V}

, if there exists

R\prec V_{i}

, the vertex corresponding to

R

is placed in the private triangular region attached to

V_{i}

. Likewise for vertices in

{\mathcal{R}}^{*}_{H}

. (b) Schema of a planar support graph.

{\mathcal{R}}^{*}_{V}=\{V_{1},\dots,V_{7}\}

,

{\mathcal{R}}^{*}_{H}=\{H_{1},\dots,H_{7}\}

,

{\mathcal{R}}_{N}=\{N_{\swarrow},N_{\nwarrow},N_{\nearrow},N_{\searrow}\}

. In comparison to Figure 11(a), here

H_{7}

is not top-aligned and

V_{5}\cap N_{\nearrow}\cap\partial P\neq\emptyset

, hence there is the edge

(V_{5},N_{\nearrow})

.

3.3 Algorithm to Draw Planar Support for ${\mathcal{R}}\setminus ker({\mathcal{R}})$

This section is an extension of Section 3. In the following we give a simple algorithm to draw a planar support of $({\mathcal{R}}\setminus ker({\mathcal{R}}),\partial P)$ . We put an edge between the left-aligned (resp. right-aligned) rectangle, if it exists, and every horizontal rectangle. Similarly, we put an edge between the top-aligned (resp. bottom-aligned) rectangle, if it exists, and every vertical rectangle. Without loss of generality, assume that all the aligned rectangles exist.

3.3.1 Placing the Vertices

Draw a circle and place the terminal vertices $V_{1},H_{1},V_{k},H_{\ell}$ on it in this order i.e., alternating between the horizontal and vertical rectangles as shown in Figure 11(a) where the circle is drawn in bold. Place the vertices corresponding to the corner rectangle between the terminal rectangles, i.e., $N_{\swarrow}$ between $V_{1}$ and $H_{1}$ , $N_{\searrow}$ between $V_{k}$ and $H_{1}$ , $N_{\nearrow}$ between $V_{k}$ and $H_{\ell}$ , and $N_{\nwarrow}$ between $V_{1}$ and $H_{\ell}$ .

Define a line joining $H_{1}$ and $H_{\ell}$ in the inner face of the cycle. Place the vertices corresponding to the other horizontal rectangles $H_{j}\in{\mathcal{R}}^{*}_{H}\setminus\{H_{1},H_{\ell}\}$ , on this line obeying the linear order defined in Definition 23. Similarly, define a line joining $V_{1}$ and $V_{k}$ in the outer face of the cycle. Place the vertices corresponding to the other vertical rectangles $V_{i}\in{\mathcal{R}}^{*}_{V}\setminus\{V_{1},V_{k}\}$ , on this line obeying the linear order defined in Definition 24.

For every $V_{i}\in{\mathcal{R}}^{*}_{V}$ , if there exists $R$ such that $R\prec V_{i}$ , then define a private region in the plane (shown by a triangle with a vertex at $V_{i}$ in Figure 11(a)). Place the vertices corresponding to all such rectangles in the $V_{i}$ ’s private region. Similarly define private regions for $H_{j}\in{\mathcal{R}}^{*}_{H}$ , if required, and place all vertices corresponding to rectangles $R$ in the region, where $H_{j}\prec R$ .

3.3.2 Drawing the Edges

1.

$({\mathcal{R}}^{*}_{V}\times{\mathcal{R}}^{*}_{H})$ . If $V_{1}$ is left-aligned with $R_{c}$ then draw an edge $(V_{1},H_{j})$ , for every $H_{j}\in{\mathcal{R}}^{*}_{H}$ as shown in Figure 11(a). Similarly, if $V_{k}$ is right-aligned then draw an edge $(V_{k},H_{j})$ , for every $H_{j}\in{\mathcal{R}}^{*}_{H}$ . Conversely, if $H_{1}$ is bottom-aligned then draw an edge $(V_{i},H_{1})$ , for every $V_{i}\in{\mathcal{R}}^{*}_{V}$ . Likewise, if $H_{\ell}$ is top-aligned then draw an edge $(V_{i},H_{\ell})$ , for every $V_{i}\in{\mathcal{R}}^{*}_{V}$ .
2.

$({\mathcal{R}}_{V}\times{\mathcal{R}}_{V})$ . If $V_{i}\cap V_{i+1}\cap\partial P\neq\emptyset$ then draw an edge $(V_{i},V_{i+1})$ for every $V_{i}\in{\mathcal{R}}^{*}_{V}$ where $1\leq i<k$ , along the line where the $V_{i}$ ’s are placed, as shown in Figure 11(a). Draw an edge $(R,V_{i})$ inside $V_{i}$ ’s private region, for every $V_{i}\in{\mathcal{R}}^{*}_{V}$ and $R\prec V_{i}$ .
3.

$({\mathcal{R}}_{H}\times{\mathcal{R}}_{H})$ . If $H_{j}\cap H_{j+1}\cap\partial P\neq\emptyset$ then draw an edge $(H_{j},H_{j+1})$ for every $H_{i}\in{\mathcal{R}}^{*}_{H}$ where $1\leq j<\ell$ , along the line where the $H_{j}$ ’s are placed, as shown in Figure 11(a). Draw an edge $(R,H_{j})$ inside $H_{j}$ ’s private region, for every $H_{j}\in{\mathcal{R}}^{*}_{H}$ and $H_{j}\prec R$ .
4.

$({\mathcal{R}}_{N}\times({\mathcal{R}}^{*}_{V}\cup{\mathcal{R}}^{*}_{H}))$ . Lemma 19 implies that if $N_{\nearrow}\cap R\cap\partial P\neq\emptyset$ where $R\in{\mathcal{R}}^{*}_{V}\cup{\mathcal{R}}^{*}_{H}$ then $R$ is either top-aligned and/or right-aligned to $R_{c}$ . If $R$ is top-aligned to $R_{c}$ and $R\in{\mathcal{R}}^{*}_{H}$ then $R=H_{\ell}$ . Draw the edge $(N_{\nearrow},H_{\ell})$ . If there exists $R^{\prime}\in{\mathcal{R}}^{*}_{V}$ such that $R^{\prime}\cap N_{\nearrow}\cap\partial P\neq\emptyset$ and $R^{\prime}$ is top-aligned with $R_{c}$ then draw the edge $(N_{\nearrow},R^{\prime})$ if $N_{\nearrow}\cap H_{\ell}\cap\partial P=\emptyset$ , otherwise do not draw the edge $(N_{\nearrow},R^{\prime})$ . See Figure 11(b). The case where $R$ is top-aligned is identical and we accordingly draw the edges. Finally, we iterate over the other corner rectangles in ${\mathcal{R}}_{N}$ and do a similar case analysis.

Lemma 30.

Given a family $({\mathcal{R}},\partial P)$ such that $ker({\mathcal{R}})\neq\emptyset$ , then $({\mathcal{R}}\setminus ker({\mathcal{R}}),\partial P)$ has a planar support.

Proof.

It is easy to see with the help of Figures 11(a) and 11(b) that the resultant graph $G$ is planar. We claim that $G$ is also a support graph. For $p\in\partial P$ consider ${\mathcal{R}}_{p}\setminus\{R_{c}\}$ . Consider $R,R^{\prime}\in{\mathcal{R}}_{p}\setminus\{R_{c}\}$ . We claim $R$ and $R^{\prime}$ are connected in $G$ .

1.

If $R,R^{\prime}\in{\mathcal{R}}_{V}$ then let $V,V^{\prime}\in{\mathcal{R}}^{*}_{V}$ such that $R\preceq V$ (i.e., $R\prec V$ or $R=V$ ) and $R^{\prime}\preceq V^{\prime}$ . From Lemma 26, $(R,V)$ and $(R^{\prime},V^{\prime})$ are edges in $G$ . This also means $V$ and $V^{\prime}$ must be consecutive in the ordering $<_{v}$ and hence they are adjacent in $G$ . Thus, $R$ and $R^{\prime}$ are connected in $G$ . Same is the case for $R,R^{\prime}\in{\mathcal{R}}_{H}$ .
2.

If $R\in{\mathcal{R}}_{V}$ and $R^{\prime}\in{\mathcal{R}}_{H}$ . Let $V\in{\mathcal{R}}^{*}_{V}$ and $H\in{\mathcal{R}}^{*}_{H}$ such that $R\prec V$ and $H\prec R^{\prime}$ . Then observe that either $V$ is a left/right aligned terminal rectangle or $H$ is a top/bottom aligned terminal rectangle, or both. In either cases, $(H,V)$ is an edge in $G$ . Hence, $R$ and $R^{\prime}$ are connected in $G$ .
3.

If $R\in{\mathcal{R}}_{N},R^{\prime}\in{\mathcal{R}}_{V}$ . Without loss of generality, let $R=N_{\nearrow}$ and let $V\in{\mathcal{R}}^{*}_{V}$ and $R\preceq V$ . From Lemma 19 there are two cases, either $V$ is top-aligned with $R_{c}$ or right-aligned with $R_{c}$ . In either cases, there is an edge drawn between $V$ and $N_{\nearrow}$ . For the former case, see Figure 11(b). For the latter case, see Figure 11(a). Thus, $R$ and $N_{\nearrow}$ are connected. The other cases involving ${\mathcal{R}}_{N}$ and ${\mathcal{R}}_{H}$ are identical.

$\hfill\blacktriangleleft$

4 Hereditary Property of Planar Boundary Supports

In this section, we prove Lemma 31, i.e., the property of the boundary supports being planar is hereditary, which in turn is used to prove Theorem 4. To that end, we need Lemmata 15, 18, and 30.

Lemma 31 (Hereditary Property).

Given a simple orthogonal polygon $P$ and a set of maximal rectangles ${\mathcal{R}}$ with respect to $P$ . If $({\mathcal{R}},\partial P)$ has a planar support then for every ${\mathcal{R}}^{\prime}\subset{\mathcal{R}}$ , $({\mathcal{R}}^{\prime},\partial P)$ also has a planar support.

Proof.

We are given a planar support graph $G$ for $({\mathcal{R}},\partial P)$ . We claim that for every $R\in{\mathcal{R}}$ , there exists a planar support graph $G^{\prime}$ for $({\mathcal{R}}\setminus\{R\},\partial P)$ . If this claim is true, then for every ${\mathcal{R}}^{\prime}\subset{\mathcal{R}}$ , $({\mathcal{R}}^{\prime},\partial P)$ also has a planar support.

Fix some $R\in{\mathcal{R}}$ and let $v$ be the vertex in $G$ corresponding to $R$ . In short, we denote $R=R(v)$ . Recall the definition of left-right coloring (Subsection 2.3). Consider a DFS tree $T$ defined on $G$ rooted at $v$ . Let $w_{i}$ be a child of $v$ in $T$ , for every $i\in[t]$ . We denote $T(w_{i})$ to be the subtree rooted at $w_{i}$ in $T$ . Let $(x_{i,j},v)$ be a cotree edge such that it points from $x_{i,j}$ to $v$ , where $x_{i,j}\in T(w_{i})$ .

From Lemma 15, we know that if $G$ is planar, then there exists a left-right coloring of the cotree edges. We do the following shortcutting operation on the cotree edges $(x_{i,j},v)$ . We replace the edge $(x_{i,j},v)$ by $(x_{i,j},w_{i})$ such that the color class of the cotree edge, in the aforesaid left-right coloring, is same as before after doing the shortcutting. See Figure 12. From Lemma 15, it follows that planarity is preserved. Let $E_{1}$ be the set of edges that we get after the shortcutting operation.

For every $p\in\partial P$ , if ${\mathcal{R}}_{p}$ lies in some subtree $T(w_{i})$ , for some $i\in[t]$ , then ${\mathcal{R}}_{p}$ is supported by this shortcutting. If the vertices corresponding to the rectangles in ${\mathcal{R}}_{p}$ are distributed across the subtrees rooted at multiple children of $v$ then observe the following.

Observation 32.

If there exist vertices $x,y\in{\mathcal{R}}_{p}$ such that $x\in T(w_{i})$ and $y\in T(w_{j})$ , for $i,j\in[t]$ and $i\neq j$ , then $w_{i},w_{j}\in{\mathcal{R}}_{p}$ .

This is true because otherwise point $p$ is not supported by $G$ . Therefore, we can ignore the descendants of $w_{i}$ , for every $i\in[t]$ and only put edges among the $w_{i}$ ’s in order to support ${\mathcal{R}}_{p}$ .

Now we can use our results from Section 3. Observe that $G[\{w_{1},\dots,w_{t},v\}]$ is a star centered at $v$ . From Lemma 18, $R$ belongs to the kernel of $(\{R(w_{1}),\dots,R(w_{t}),R\},\partial P)$ , where $R=R(v)$ . Furthermore, from Lemma 30, $(\{R(w_{1}),\dots,R(w_{t})\},\partial P)$ has a planar support. Let $E_{2}$ be the edge set of this support (drawn in red in Figure 12).

Thus, $G^{\prime}:=({\mathcal{R}}\setminus\{R\},E_{1}\cup E_{2})$ is a support of $({\mathcal{R}}\setminus\{R\},\partial P)$ . $G^{\prime}$ is also planar because an edge in $E_{1}$ and that in $E_{2}$ can be drawn without crossing each other. As for every distinct $i,j\in[t]$ , edges in $E(T(w_{i}))$ can be drawn in their private regions which are disjoint to that of $E(T(w_{j}))$ . Finally, the edges in $E_{2}$ can be drawn outside the union of these private regions. $\hfill\blacktriangleleft$

Figure 12: On the left, there is a schematic diagram of

G

, the support graph of

({\mathcal{R}},\partial P)

. On the right, there is a schematic diagram of

G^{\prime}

, the support graph of

({\mathcal{R}}\setminus\{R\},\partial P)

.

G^{\prime}

is obtained from

G

by shortcutting the cotree edges (drawn in blue), incoming to

v

, and adding the edges in

E_{2}

(red edges among

w_{j}

’s) such that

(\{R(w_{1}),\dots,R(w_{t})\},\partial P)

has a planar support.

5 Complete Family of Maximal Rectangles

In this section, we state Lemma 33 and give a proof sketch. This lemma is used to prove Theorem 4. Refer to [45] for the full proof of the lemma. Recall that for a simple orthogonal polygon $P$ , ${\mathcal{R}}^{K}(P)$ is the set of all maximal rectangles with respect to $P$ .

Lemma 33.

$({\mathcal{R}}^{K}(P),\partial P)$ has a planar support.

Proof Sketch.

Given an orthogonal polygon $P$ , we show that if the statement is true for a subpolygon $P^{\prime}\subset P$ , where $P\setminus P^{\prime}$ is a rectangle, then it also true for $P$ . Thus, inductively one can argue that if $G_{P^{\prime}}$ is a planar support for $({\mathcal{R}}^{K}(P^{\prime}),\partial P^{\prime})$ then there exists a planar support $G_{P}$ for $({\mathcal{R}}^{K}(P),\partial P)$ . In particular, given $G_{P^{\prime}}$ as an input, we give an algorithm to draw $G_{P}$ . We make a number of observations between the interplay of the rectangle families in $P$ and $P^{\prime}$ , and their corresponding support graphs. We observe that the new rectangles that are part of $P$ but not in $P^{\prime}$ have a unique rectangle in $P^{\prime}$ that share common blockers in one or two sides; let’s call them the old rectangles in $P^{\prime}$ . Owing to which, we need to put an edge between every such new-old pair in $G_{P}$ . We further observe that in any support graph for $P$ ( $P^{\prime}$ resp.) these new (old resp.) rectangles induce a path in $G_{P}$ ( $G_{P^{\prime}}$ resp.). Lastly, we need to remove a set of vertices for which an old vertex acts as a cut vertex in $G_{P^{\prime}}$ and make them adjacent to their new counterpart. We carefully argue that these sequence of operations ensure that the resultant graph $G_{P}$ is a planar support for $({\mathcal{R}}^{K}(P),\partial P)$ . $\hfill\blacktriangleleft$

6 Planar Support Graphs and its Implications

Finally we present our main result.

Theorem 4 (Planar Support for Boundary Cover). [Restated, see original statement.]

Given a simple orthogonal polygon $P$ and a set of containment-maximal rectangles ${\mathcal{R}}$ with respect to $P$ , there exists a planar support graph for $({\mathcal{R}},\partial P)$ .

Proof.

From Lemma 33 it follows that $({\mathcal{R}}^{K}(P),\partial P)$ has a planar support. By applying Lemma 31 we prove that $({\mathcal{R}},\partial P)$ has a planar support, as ${\mathcal{R}}\subseteq{\mathcal{R}}^{K}(P)$ . $\hfill\blacktriangleleft$

Theorem 4 and Lemma 10 together implies Theorems 1 and 2.

Theorem 1. [Restated, see original statement.]

Local Search yields a PTAS for the Boundary Cover problem for simple orthogonal polygons.

Theorem 2. [Restated, see original statement.]

Local Search yields a PTAS for the Corner Cover problem for simple orthogonal polygons.

Similarly, Theorem 4 and Lemma 11 together implies Theorem 3.

Theorem 3. [Restated, see original statement.]

Local Search yields a PTAS for the Maximum Independent Set problem on the geometric hypergraph $({\mathcal{R}},\partial P)$ .

Proof.

From Lemma 11, we know that if the intersection graph of the union of the optimum and the Local Search solution is planar, then Theorem 3 follows.

As both optimum and Local Search solutions are independent sets, every point in $\partial P$ is contained in at most $2$ rectangles. Thus, the support graph of their union is the intersection graph. Therefore, from Theorem 4 the planarity of the intersection graph of their union follows. Hence proved. $\hfill\blacktriangleleft$

7 Negative Results

We have the following negative results.

Theorem 5. [Restated, see original statement.]

For every $r\geq 3$ , there exists simple orthogonal polygon $P$ and an interior cover ${\mathcal{R}}$ such that every arbitrary support graph of $({\mathcal{R}},P)$ contains $K_{r,r}$ .

Proof.

See Figure 13(a). For $r\geq 3$ , one can construct a simple polygon $P$ and define a set of maximal rectangles as shown in Figure 13(a) such that the minimal interior support graph is $K_{r,r}$ . $\hfill\blacktriangleleft$

(a) A simple polygon

P

with

{\mathcal{R}}=\{A,B,C,D,P,Q,R,S\}

.
The minimal support graph of

({\mathcal{R}},P)

is

K_{4,4}

.

(b) A schematic diagram of a polygon whose top-right quadrant has

r

corners and its bottom-left quadrant has

s

corners.

Figure 13: Instances that lead to (arbitrarily large) bicliques in the support graphs of the Interior Cover (left) and the Antirectangle problem (right).

Recall the visibility graph that we defined in Section 1.2.

Lemma 34.

For every $r,s\geq 3$ , there exists a simple polygon $P$ and a finite point set $Q\subset P$ such that $Q$ is a union of two antirectangles and the visibility graph defined on $Q$ is $K_{r,s}$ .

Proof.

See Figure 13(b). Observe that the set of convex corners in the top-right (resp. bottom-left) quadrant forms an antirectangle. Also, observe that for every pair of corner, one from the top-right quadrant and the other from the bottom-left quadrant, there exist a rectangle containing them and in $P$ . $\hfill\blacktriangleleft$

Lemma 34 implies the following.

Theorem 6. [Restated, see original statement.]

There exist simple polygons for which the local optimum solution size can be arbitrarily smaller than that of the global optimum solution for the Maximum Antirectangle problem.

Proof.

Consider Figure 13(b). Assume $r=\Omega(n)$ and $s=O(\log n)$ . The global optimum solution size is $\geq r$ , one such solution is picking all the convex corners of the polygon in the top-right quadrant. If the initial feasible solution for the Local Search algorithm is the set of corners in the bottom-left quadrant, then it can never improve its solution and that would be the local optimum solution. $\hfill\blacktriangleleft$

Theorem 7. [Restated, see original statement.]

There exist simple polygons for which the local optimum solution size can be arbitrarily larger than that of the global optimum solution for the Minimum Hitting Set problem for $(\partial P,{\mathcal{R}})$ .

Proof.

See Figure 13(b). Observe that the set of convex corners in the top-right (resp. bottom-left) quadrant forms a hitting set set. As in proof of Theorem 6, assume $r=\Omega(n)$ and $s=O(\log n)$ . The global optimum solution size is $\leq s$ , one such solution is picking all the convex corners of the polygon in the bottom-left quadrant. If the initial feasible solution for the Local Search algorithm is the set of corners in the top-right quadrant, then it can never improve its solution and that would be the local optimum solution. $\hfill\blacktriangleleft$

References

[1] Mikkel Abrahamsen. Covering polygons is even harder. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 375–386. IEEE, IEEE, 2021. doi:10.1109/FOCS52979.2021.00045.
[2] Anna Adamaszek and Andreas Wiese. Approximation schemes for maximum weight independent set of rectangles. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 400–409. IEEE, 2013. doi:10.1109/FOCS.2013.50.
[3] Pankaj K. Agarwal, Marc van Kreveld, and Subhash Suri. Label placement by maximum independent set in rectangles. Computational Geometry, 11(3):209–218, 1998. doi:10.1016/S0925-7721(98)00028-5.
[4] David A Applegate, Gruia Calinescu, David S Johnson, Howard Karloff, Katrina Ligett, and Jia Wang. Compressing rectilinear pictures and minimizing access control lists. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1066–1075, 2007. URL: http://dl.acm.org/citation.cfm?id=1283383.1283498.
[5] Boris Aronov, Esther Ezra, and Micha Sharir. Small-size $\varepsilon$ -nets for axis-parallel rectangles and boxes. SIAM J. Comput., 39(7):3248–3282, 2010. doi:10.1137/090762968.
[6] Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit. Local search heuristic for k-median and facility location problems. In STOC, pages 21–29, 2001. doi:10.1145/380752.380755.
[7] Rom Aschner, Matthew J Katz, Gila Morgenstern, and Yelena Yuditsky. Approximation schemes for covering and packing. In International Workshop on Algorithms and Computation, pages 89–100. Springer, 2013. doi:10.1007/978-3-642-36065-7_10.
[8] Pradeesha Ashok, Aniket Basu Roy, and Sathish Govindarajan. Local search strikes again: Ptas for variants of geometric covering and packing. Journal of Combinatorial Optimization, 39(2):618–635, 2020. doi:10.1007/s10878-019-00432-y.
[9] Stav Ashur, Omrit Filtser, Matthew J Katz, and Rachel Saban. Terrain-like graphs: PTASs for guarding weakly-visible polygons and terrains. Computational Geometry, 101:101832, 2022. doi:10.1016/j.comgeo.2021.101832.
[10] Aniket Basu Roy, Sathish Govindarajan, Rajiv Raman, and Saurabh Ray. Packing and covering with non-piercing regions. Discrete & Computational Geometry, 60:471–492, 2018. doi:10.1007/s00454-018-9983-2.
[11] Piotr Berman and Bhaskar DasGupta. Complexities of efficient solutions of rectilinear polygon cover problems. Algorithmica, 17:331–356, 1997. doi:10.1007/BF02523677.
[12] Hervé Brönnimann and Michael T. Goodrich. Almost optimal set covers in finite VC-dimension. Discrete & Computational Geometry, 14(1):463–479, 1995. doi:10.1007/BF02570718.
[13] Reilly Browne, Prahlad Narasimhan Kasthurirangan, Joseph S. B. Mitchell, and Valentin Polishchuk. Constant-factor approximation algorithms for convex cover and hidden set in a simple polygon. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 1357–1365. IEEE, IEEE, 2023. doi:10.1109/FOCS57990.2023.00083.
[14] Kevin Buchin, Marc J van Kreveld, Henk Meijer, Bettina Speckmann, and KAB Verbeek. On planar supports for hypergraphs. Journal of Graph Algorithms and Applications, 15(4):533–549, 2011. doi:10.7155/jgaa.00237.
[15] Seth Chaiken, Daniel J Kleitman, Michael Saks, and James Shearer. Covering regions by rectangles. SIAM Journal on Algebraic Discrete Methods, 2(4):394–410, 1981.
[16] Parinya Chalermsook and Julia Chuzhoy. Maximum independent set of rectangles. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 892–901. SIAM, 2009. doi:10.1137/1.9781611973068.97.
[17] Timothy M Chan. Conflict-free coloring of points with respect to rectangles and approximation algorithms for discrete independent set. In Proceedings of the Twenty-Eighth Annual Symposium on Computational Geometry, pages 293–302, 2012. doi:10.1145/2261250.2261293.
[18] Timothy M Chan and Elyot Grant. Exact algorithms and APX-hardness results for geometric packing and covering problems. Computational Geometry, 47(2):112–124, 2014. doi:10.1016/j.comgeo.2012.04.001.
[19] Timothy M Chan, Elyot Grant, Jochen Könemann, and Malcolm Sharpe. Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 1576–1585. SIAM, 2012. doi:10.1137/1.9781611973099.125.
[20] Timothy M. Chan and Sariel Har-Peled. Approximation algorithms for maximum independent set of pseudo-disks. Discrete & Computational Geometry, 48(2):373–392, 2012. doi:10.1007/s00454-012-9417-5.
[21] Kenneth L Clarkson and Kasturi Varadarajan. Improved approximation algorithms for geometric set cover. Discrete & Computational Geometry, 37(1):43–58, 2007. doi:10.1007/s00454-006-1273-8.
[22] H Conn and J O’Rourke. Some restricted rectangle covering problems. In Proceedings of the 1987 Allerton Conference, 1987.
[23] Joseph C Culberson and Robert A Reckhow. Covering polygons is hard. J. Algorithms, 17(1):2–44, 1994. doi:10.1006/jagm.1994.1025.
[24] Hubert De Fraysseix, Patrice Ossona De Mendez, and Pierre Rosenstiehl. Trémaux trees and planarity. International Journal of Foundations of Computer Science, 17(05):1017–1029, 2006. doi:10.1142/S0129054106004248.
[25] Stephane Durocher and Robert Fraser. Duality for geometric set cover and geometric hitting set problems on pseudodisks. In Proceedings of the 27th Canadian Conference on Computational Geometry, CCCG 2015, Kingston, Ontario, Canada, August 10-12, 2015. Queen’s University, Ontario, Canada, 2015. URL: http://research.cs.queensu.ca/cccg2015/CCCG15-papers/10.pdf.
[26] Alina Ene, Sariel Har-Peled, and Benjamin Raichel. Geometric packing under nonuniform constraints. SIAM Journal on Computing, 46(6):1745–1784, 2017. doi:10.1137/120898413.
[27] Deborah S. Franzblau. Performance guarantees on a sweep-line heuristic for covering rectilinear polygons with rectangles. SIAM Journal on Discrete Mathematics, 2(3):307–321, 1989. doi:10.1137/0402027.
[28] M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences. W. H. Freeman, 1979. A guide to the theory of NP-completeness.
[29] Anupam Gupta and Kanat Tangwongsan. Simpler analyses of local search algorithms for facility location. CoRR, abs/0809.2554, 2008. doi:10.48550/arXiv.0809.2554.
[30] Waldo Gálvez, Arindam Khan, Mathieu Mari, Tobias Mömke, Madhusudhan Reddy, and Andreas Wiese. A (2+ $\epsilon$ )-approximation algorithm for maximum independent set of rectangles, 2021. doi:10.48550/arXiv.2106.00623.
[31] Kathrin Hanauer, Martin P Seybold, and Julian Unterweger. Covering rectilinear polygons with area-weighted rectangles. In 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX), pages 157–169. SIAM, 2024. doi:10.1137/1.9781611977929.12.
[32] Sariel Har-Peled and Kent Quanrud. Approximation algorithms for polynomial-expansion and low-density graphs. In Algorithms – ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14–16, 2015, Proceedings, pages 717–728, 2015. doi:10.1007/978-3-662-48350-3_60.
[33] D Haussler and Emo Welzl. $\epsilon$ -nets and simplex range queries. Discret. Comput. Geom., 2:127–151, 1987. doi:10.1007/BF02187876.
[34] Laura Heinrich-Litan and Marco E. Lübbecke. Rectangle covers revisited computationally. ACM J. Exp. Algorithmics, 11:2.6–es, February 2007. doi:10.1145/1187436.1216583.
[35] David S Johnson and Henry O Pollak. Hypergraph planarity and the complexity of drawing venn diagrams. Journal of Graph Theory, 11(3):309–325, 1987. doi:10.1002/jgt.3190110306.
[36] Michael Kaufmann, Marc van Kreveld, and Bettina Speckmann. Subdivision drawings of hypergraphs. In International Symposium on Graph Drawing, pages 396–407. Springer, 2008. doi:10.1007/978-3-642-00219-9_39.
[37] Ivo Koch and Javier Marenco. A hybrid heuristic for the rectilinear picture compression problem. 4OR, 21(2):329–358, 2023. doi:10.1007/s10288-022-00515-3.
[38] Erik Krohn, Matt Gibson, Gaurav Kanade, and Kasturi Varadarajan. Guarding terrains via local search. Journal of Computational Geometry, 5(1):168–178, 2014. doi:10.20382/jocg.v5i1a9.
[39] VS Anil Kumar and H Ramesh. Covering rectilinear polygons with axis-parallel rectangles. SIAM Journal on Computing, 32(6):1509–1541, 2003. doi:10.1137/S0097539799358835.
[40] Joseph S. B. Mitchell. Approximating maximum independent set for rectangles in the plane. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 339–350. IEEE, 2021. doi:10.1109/FOCS52979.2021.00042.
[41] Nabil H. Mustafa and Saurabh Ray. Improved results on geometric hitting set problems. Discrete & Computational Geometry, 44(4):883–895, 2010. doi:10.1007/s00454-010-9285-9.
[42] János Pach and Gábor Tardos. Tight lower bounds for the size of epsilon-nets. In Proceedings of the twenty-Seventh Annual Symposium on Computational Geometry, pages 458–463, 2011. doi:10.1145/1998196.1998271.
[43] Rajiv Raman and Saurabh Ray. Constructing planar support for non-piercing regions. Discrete & Computational Geometry, 64(3):1098–1122, 2020. doi:10.1007/s00454-020-00216-w.
[44] Rajiv Raman and Karamjeet Singh. On hypergraph supports. CoRR, abs/2303.16515, 2023. doi:10.48550/arXiv.2303.16515.
[45] Aniket Basu Roy. Covering simple orthogonal polygons with rectangles. CoRR, abs/2406.16209, 2024. doi:10.48550/arXiv.2406.16209.
[46] Manuel Combarro Simón, Pierre Talbot, Grégoire Danoy, Jedrzej Musial, Mohammed Alswaitti, and Pascal Bouvry. Constraint model for the satellite image mosaic selection problem (short paper). In Roland H. C. Yap, editor, 29th International Conference on Principles and Practice of Constraint Programming, CP 2023, August 27-31, 2023, Toronto, Canada, volume 280 of LIPIcs, pages 44:1–44:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.CP.2023.44.
[47] Kasturi Varadarajan. Weighted geometric set cover via quasi-uniform sampling. In Proceedings of the Forty-Second ACM Symposium on Theory of Computing, pages 641–648, 2010. doi:10.1145/1806689.1806777.

[bib.bib1] [1] Mikkel Abrahamsen. Covering polygons is even harder. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 375–386. IEEE, IEEE, 2021. doi:10.1109/FOCS52979.2021.00045.

[bib.bib2] [2] Anna Adamaszek and Andreas Wiese. Approximation schemes for maximum weight independent set of rectangles. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 400–409. IEEE, 2013. doi:10.1109/FOCS.2013.50.

[bib.bib3] [3] Pankaj K. Agarwal, Marc van Kreveld, and Subhash Suri. Label placement by maximum independent set in rectangles. Computational Geometry, 11(3):209–218, 1998. doi:10.1016/S0925-7721(98)00028-5.

[bib.bib4] [4] David A Applegate, Gruia Calinescu, David S Johnson, Howard Karloff, Katrina Ligett, and Jia Wang. Compressing rectilinear pictures and minimizing access control lists. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1066–1075, 2007. URL: http://dl.acm.org/citation.cfm?id=1283383.1283498.

[bib.bib5] [5] Boris Aronov, Esther Ezra, and Micha Sharir. Small-size $\varepsilon$ -nets for axis-parallel rectangles and boxes. SIAM J. Comput., 39(7):3248–3282, 2010. doi:10.1137/090762968.

[bib.bib6] [6] Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit. Local search heuristic for k-median and facility location problems. In STOC, pages 21–29, 2001. doi:10.1145/380752.380755.

[bib.bib7] [7] Rom Aschner, Matthew J Katz, Gila Morgenstern, and Yelena Yuditsky. Approximation schemes for covering and packing. In International Workshop on Algorithms and Computation, pages 89–100. Springer, 2013. doi:10.1007/978-3-642-36065-7_10.

[bib.bib8] [8] Pradeesha Ashok, Aniket Basu Roy, and Sathish Govindarajan. Local search strikes again: Ptas for variants of geometric covering and packing. Journal of Combinatorial Optimization, 39(2):618–635, 2020. doi:10.1007/s10878-019-00432-y.

[bib.bib9] [9] Stav Ashur, Omrit Filtser, Matthew J Katz, and Rachel Saban. Terrain-like graphs: PTASs for guarding weakly-visible polygons and terrains. Computational Geometry, 101:101832, 2022. doi:10.1016/j.comgeo.2021.101832.

[bib.bib10] [10] Aniket Basu Roy, Sathish Govindarajan, Rajiv Raman, and Saurabh Ray. Packing and covering with non-piercing regions. Discrete & Computational Geometry, 60:471–492, 2018. doi:10.1007/s00454-018-9983-2.

[bib.bib11] [11] Piotr Berman and Bhaskar DasGupta. Complexities of efficient solutions of rectilinear polygon cover problems. Algorithmica, 17:331–356, 1997. doi:10.1007/BF02523677.

[bib.bib12] [12] Hervé Brönnimann and Michael T. Goodrich. Almost optimal set covers in finite VC-dimension. Discrete & Computational Geometry, 14(1):463–479, 1995. doi:10.1007/BF02570718.

[bib.bib13] [13] Reilly Browne, Prahlad Narasimhan Kasthurirangan, Joseph S. B. Mitchell, and Valentin Polishchuk. Constant-factor approximation algorithms for convex cover and hidden set in a simple polygon. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 1357–1365. IEEE, IEEE, 2023. doi:10.1109/FOCS57990.2023.00083.

[bib.bib14] [14] Kevin Buchin, Marc J van Kreveld, Henk Meijer, Bettina Speckmann, and KAB Verbeek. On planar supports for hypergraphs. Journal of Graph Algorithms and Applications, 15(4):533–549, 2011. doi:10.7155/jgaa.00237.

[bib.bib15] [15] Seth Chaiken, Daniel J Kleitman, Michael Saks, and James Shearer. Covering regions by rectangles. SIAM Journal on Algebraic Discrete Methods, 2(4):394–410, 1981.

[bib.bib16] [16] Parinya Chalermsook and Julia Chuzhoy. Maximum independent set of rectangles. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 892–901. SIAM, 2009. doi:10.1137/1.9781611973068.97.

[bib.bib17] [17] Timothy M Chan. Conflict-free coloring of points with respect to rectangles and approximation algorithms for discrete independent set. In Proceedings of the Twenty-Eighth Annual Symposium on Computational Geometry, pages 293–302, 2012. doi:10.1145/2261250.2261293.

[bib.bib18] [18] Timothy M Chan and Elyot Grant. Exact algorithms and APX-hardness results for geometric packing and covering problems. Computational Geometry, 47(2):112–124, 2014. doi:10.1016/j.comgeo.2012.04.001.

[bib.bib19] [19] Timothy M Chan, Elyot Grant, Jochen Könemann, and Malcolm Sharpe. Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 1576–1585. SIAM, 2012. doi:10.1137/1.9781611973099.125.

[bib.bib20] [20] Timothy M. Chan and Sariel Har-Peled. Approximation algorithms for maximum independent set of pseudo-disks. Discrete & Computational Geometry, 48(2):373–392, 2012. doi:10.1007/s00454-012-9417-5.

[bib.bib21] [21] Kenneth L Clarkson and Kasturi Varadarajan. Improved approximation algorithms for geometric set cover. Discrete & Computational Geometry, 37(1):43–58, 2007. doi:10.1007/s00454-006-1273-8.

[bib.bib22] [22] H Conn and J O’Rourke. Some restricted rectangle covering problems. In Proceedings of the 1987 Allerton Conference, 1987.

[bib.bib23] [23] Joseph C Culberson and Robert A Reckhow. Covering polygons is hard. J. Algorithms, 17(1):2–44, 1994. doi:10.1006/jagm.1994.1025.

[bib.bib24] [24] Hubert De Fraysseix, Patrice Ossona De Mendez, and Pierre Rosenstiehl. Trémaux trees and planarity. International Journal of Foundations of Computer Science, 17(05):1017–1029, 2006. doi:10.1142/S0129054106004248.

[bib.bib25] [25] Stephane Durocher and Robert Fraser. Duality for geometric set cover and geometric hitting set problems on pseudodisks. In Proceedings of the 27th Canadian Conference on Computational Geometry, CCCG 2015, Kingston, Ontario, Canada, August 10-12, 2015. Queen’s University, Ontario, Canada, 2015. URL: http://research.cs.queensu.ca/cccg2015/CCCG15-papers/10.pdf.

[bib.bib26] [26] Alina Ene, Sariel Har-Peled, and Benjamin Raichel. Geometric packing under nonuniform constraints. SIAM Journal on Computing, 46(6):1745–1784, 2017. doi:10.1137/120898413.

[bib.bib27] [27] Deborah S. Franzblau. Performance guarantees on a sweep-line heuristic for covering rectilinear polygons with rectangles. SIAM Journal on Discrete Mathematics, 2(3):307–321, 1989. doi:10.1137/0402027.

[bib.bib28] [28] M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences. W. H. Freeman, 1979. A guide to the theory of NP-completeness.

[bib.bib29] [29] Anupam Gupta and Kanat Tangwongsan. Simpler analyses of local search algorithms for facility location. CoRR, abs/0809.2554, 2008. doi:10.48550/arXiv.0809.2554.

[bib.bib30] [30] Waldo Gálvez, Arindam Khan, Mathieu Mari, Tobias Mömke, Madhusudhan Reddy, and Andreas Wiese. A (2+ $\epsilon$ )-approximation algorithm for maximum independent set of rectangles, 2021. doi:10.48550/arXiv.2106.00623.

[bib.bib31] [31] Kathrin Hanauer, Martin P Seybold, and Julian Unterweger. Covering rectilinear polygons with area-weighted rectangles. In 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX), pages 157–169. SIAM, 2024. doi:10.1137/1.9781611977929.12.

[bib.bib32] [32] Sariel Har-Peled and Kent Quanrud. Approximation algorithms for polynomial-expansion and low-density graphs. In Algorithms – ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14–16, 2015, Proceedings, pages 717–728, 2015. doi:10.1007/978-3-662-48350-3_60.

[bib.bib33] [33] D Haussler and Emo Welzl. $\epsilon$ -nets and simplex range queries. Discret. Comput. Geom., 2:127–151, 1987. doi:10.1007/BF02187876.

[bib.bib34] [34] Laura Heinrich-Litan and Marco E. Lübbecke. Rectangle covers revisited computationally. ACM J. Exp. Algorithmics, 11:2.6–es, February 2007. doi:10.1145/1187436.1216583.

[bib.bib35] [35] David S Johnson and Henry O Pollak. Hypergraph planarity and the complexity of drawing venn diagrams. Journal of Graph Theory, 11(3):309–325, 1987. doi:10.1002/jgt.3190110306.

[bib.bib36] [36] Michael Kaufmann, Marc van Kreveld, and Bettina Speckmann. Subdivision drawings of hypergraphs. In International Symposium on Graph Drawing, pages 396–407. Springer, 2008. doi:10.1007/978-3-642-00219-9_39.

[bib.bib37] [37] Ivo Koch and Javier Marenco. A hybrid heuristic for the rectilinear picture compression problem. 4OR, 21(2):329–358, 2023. doi:10.1007/s10288-022-00515-3.

[bib.bib38] [38] Erik Krohn, Matt Gibson, Gaurav Kanade, and Kasturi Varadarajan. Guarding terrains via local search. Journal of Computational Geometry, 5(1):168–178, 2014. doi:10.20382/jocg.v5i1a9.

[bib.bib39] [39] VS Anil Kumar and H Ramesh. Covering rectilinear polygons with axis-parallel rectangles. SIAM Journal on Computing, 32(6):1509–1541, 2003. doi:10.1137/S0097539799358835.

[bib.bib40] [40] Joseph S. B. Mitchell. Approximating maximum independent set for rectangles in the plane. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 339–350. IEEE, 2021. doi:10.1109/FOCS52979.2021.00042.

[bib.bib41] [41] Nabil H. Mustafa and Saurabh Ray. Improved results on geometric hitting set problems. Discrete & Computational Geometry, 44(4):883–895, 2010. doi:10.1007/s00454-010-9285-9.

[bib.bib42] [42] János Pach and Gábor Tardos. Tight lower bounds for the size of epsilon-nets. In Proceedings of the twenty-Seventh Annual Symposium on Computational Geometry, pages 458–463, 2011. doi:10.1145/1998196.1998271.

[bib.bib43] [43] Rajiv Raman and Saurabh Ray. Constructing planar support for non-piercing regions. Discrete & Computational Geometry, 64(3):1098–1122, 2020. doi:10.1007/s00454-020-00216-w.

[bib.bib44] [44] Rajiv Raman and Karamjeet Singh. On hypergraph supports. CoRR, abs/2303.16515, 2023. doi:10.48550/arXiv.2303.16515.

[bib.bib45] [45] Aniket Basu Roy. Covering simple orthogonal polygons with rectangles. CoRR, abs/2406.16209, 2024. doi:10.48550/arXiv.2406.16209.

[bib.bib46] [46] Manuel Combarro Simón, Pierre Talbot, Grégoire Danoy, Jedrzej Musial, Mohammed Alswaitti, and Pascal Bouvry. Constraint model for the satellite image mosaic selection problem (short paper). In Roland H. C. Yap, editor, 29th International Conference on Principles and Practice of Constraint Programming, CP 2023, August 27-31, 2023, Toronto, Canada, volume 280 of LIPIcs, pages 44:1–44:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.CP.2023.44.

[bib.bib47] [47] Kasturi Varadarajan. Weighted geometric set cover via quasi-uniform sampling. In Proceedings of the Forty-Second ACM Symposium on Theory of Computing, pages 641–648, 2010. doi:10.1145/1806689.1806777.

Covering Simple Orthogonal Polygons with Rectangles

Abstract

Keywords and phrases:

Category:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

1.1 Our Contribution

Theorem 1.

Theorem 2.

Theorem 3.

Theorem 4 (Planar Support for Boundary Cover).

Theorem 5.

Theorem 6.

Theorem 7.

1.1.1 Technical Overview and Organization

1.2 Related Work

2 Preliminaries

Definition 8 (Blocker of a Maximal Rectangle).

Definition 9 (Support graph of a hypergraph).

2.1 Local Search Framework

Lemma 10.

Lemma 11.

2.2 Intersection Patterns

Definition 12.

2.3 Left-Right Coloring

Definition 13 (DFS-orientation).

Definition 14 (Left-Right Coloring).

Lemma 15 ([24]).

3 Family of Rectangles with a Kernel

Definition 16 (Kernel of a Family).

Observation 17.

Lemma 18.

Proof.

Lemma 19.

Proof.

Observation 20.

Lemma 21.

Proof.

3.1 Vertical and Horizontal Rectangles

Lemma 22.

Proof.

Definition 23.

Definition 24.

Lemma 25.

Proof.

Lemma 26.

Proof.

3.2 Intersection between Corner and Non-corner Rectangles

Lemma 27.

Proof.

Lemma 28.

Proof.

▶ Remark 29.

3.3 Algorithm to Draw Planar Support for 𝓡∖𝒌⁢𝒆⁢𝒓⁢(𝓡)

3.3.1 Placing the Vertices

3.3.2 Drawing the Edges

Lemma 30.

Proof.

4 Hereditary Property of Planar Boundary Supports

Lemma 31 (Hereditary Property).

Proof.

Observation 32.

5 Complete Family of Maximal Rectangles

Lemma 33.

Proof Sketch.

6 Planar Support Graphs and its Implications

Theorem 4 (Planar Support for Boundary Cover). [Restated, see original statement.]

Proof.

Theorem 1. [Restated, see original statement.]

Theorem 2. [Restated, see original statement.]

Theorem 3. [Restated, see original statement.]

Proof.

$\blacktriangleright$ Remark 29.

3.3 Algorithm to Draw Planar Support for ${\mathcal{R}}\setminus ker({\mathcal{R}})$