IDSIA, USI-SUPSI, Switzerland and
<EMAIL_ADDRESS>IDSIA, USI-SUPSI,
Switzerland and<EMAIL_ADDRESS>LIRMM, University
of Montpellier, CNRS, Montpellier, France and
<EMAIL_ADDRESS>IDSIA, USI-SUPSI,
<EMAIL_ADDRESS>Fabrizio Grandoni, Edin Husić, Mathieu
Mari and Antoine Tinguely Theory of computation Packing and covering problems

# Approximating the Maximum Independent Set of Convex Polygons with a Bounded
Number of Directions

Fabrizio Grandoni  Edin Husić  Mathieu Mari  Antoine Tinguely

###### Abstract

In the maximum independent set of convex polygons problem, we are given a set
of $n$ convex polygons in the plane with the objective of selecting a maximum
cardinality subset of non-overlapping polygons. Here we study a special case
of the problem where the edges of the polygons can take at most $d$ fixed
directions. We present an $8d/3$-approximation algorithm for this problem
running in time $O((nd)^{O(d4^{d})})$. The previous-best polynomial-time
approximation (for constant $d$) was a classical $n^{\varepsilon}$
approximation by Fox and Pach [SODA’11] that has recently been improved to a
$\operatorname{OPT}^{\varepsilon}$-approximation algorithm by Cslovjecsek,
Pilipczuk and Węgrzycki [SODA ’24], which also extends to an arbitrary set of
convex polygons.

Our result builds on, and generalizes the recent constant factor approximation
algorithms for the maximum independent set of axis-parallel rectangles problem
(which is a special case of our problem with $d=2$) by Mitchell [FOCS’21] and
Gálvez, Khan, Mari, Mömke, Reddy, and Wiese [SODA’22].

###### keywords:

Approximation algorithms, independent set, polygons

##  1 Introduction

The Maximum Independent Set of Convex Polygons problem (MISP) is a natural
geometric packing problem with many applications in map labeling [13, 39],
cellular networks [34], unsplittable flow [6], chip manufacturing [27], or
data mining [18, 33]. Given a set of $n$ convex polygons in the plane, the
goal is to select a maximum number of them such that the polygons are pairwise
non-overlapping.

MISP is NP-hard [16, 28], hence it makes sense to design approximation
algorithms for it. Disappointingly, the best (polynomial-time) approximation
ratio for MISP (more precisely for $k$-intersecting curves) has been
$n^{\varepsilon}$ [17], for any fixed constant $\varepsilon>0$. This ratio has
recently been improved to $\operatorname{OPT}^{\varepsilon}$ [12].

Approximation Schemes. Interestingly, there is a quasi-polynomial time
approximation scheme (QPTAS) for MISP [1] (if the polygons have at most quasi-
polynomially many vertices in total). Thus, the problem is _not_ APX-Hard,
assuming $\mathrm{NP}\nsubseteq\mathrm{DTIME}(2^{\textrm{polylog}(n)})$,
suggesting that it should be possible to obtain a polynomial time
approximation scheme (PTAS) for the problem.

If we assume that we are allowed to shrink the polygons by a factor $1-\delta$
for an arbitrarily small constant $\delta$, then there is a PTAS for the
problem [40]. Note that here the output is compared to the optimal solution
without shrinking.

When the input polygons are fat, e.g., regular polygons, then PTASes are known
[9, 15].

Axis-parallel rectangles. A prominent special case of MISP that has attracted
a lot of attention over the years is the maximum independent set of axis-
parallel rectangles (MISR), where all the polygons are rectangles with their
edges parallel with the axes. An $O(\log n)$ approximation for MISR was given
in [30, 38]. This was slightly improved to $O(\log n/\log\log n)$ in [10], and
substantially improved to $O(\log\log n)$ in [7]. In a recent breakthrough
result, Mitchell [36] presented the first constant factor approximation
algorithm with approximation ratio $10$, and later $3+\varepsilon$ in an
updated version [37] with a considerably shorter case analysis. Subsequently,
his approach was simplified and improved to a $(2+\varepsilon)$-approximation
algorithm by Gálvez, Khan, Mari, Mömke, Reddy, and Wiese [21, 22]. These
approaches rely on a dynamic program that considers all the partitions of a
bounding box containing the instance into a number of containers with constant
complexity (constant number of line segments).

Our contribution. With the goal of better understanding the approximability of
MISP, in this paper, we consider the following natural special case of MISP:
$d$-MISP is the special case of MISP where the edges of the input polygons are
parallel to a given set $\mathcal{D}$ of $d=|\mathcal{D}|$ directions. Notice
that MISR is equivalent to $2$-MISP. Our main result is a constant
approximation for $d$-MISP when $d$ is a constant.

######  Theorem 1.1.

There exists an $8d/3$-approximation algorithm for $d$-MISP running in time
$O((nd)^{O(d4^{d})})$.

Our result builds on the approaches in [21, 22, 37], however we have to face
several additional complications. In particular, already for $d=3$ the
algorithm and its analysis deviates substantially from the known (polynomial-
time) results in the literature about axis-aligned rectangles. An overview of
our approach is given in Section 3.

Related Work. One can consider a natural weighted version of MISP, where each
convex polygon has a positive weight, and the goal is to find an independent
set of maximum total weight. The weighted version of MISR was studied in the
literature, and the current-best polynomial time approximation factor is
$O(\log\log n)$ [8]. We remark that our approach, likewise the approaches in
[21, 22, 36], does not seem to extend to the weighted case. In particular,
finding a constant approximation for weighted MISR remains a challenging open
problem. We remark that the QPTAS in [1] extends to the weighted case, hence
suggesting that the weighted version of MISP might also admit a PTAS.

MISR was also studied in terms of parameterized algorithms. Marx [35] proved
that the problem is W[1]-hard, which rules out the existence of an EPTAS. A
parameterized approximation scheme for the problem is given in [23].

A rectangle packing problem related to MISR is the 2D Knapsack problem. Here
we are given an axis-parallel square (the _knapsack_) and a collection of
axis-parallel rectangles. The goal is to pack a maximum cardinality (or
weight) subset of rectangles in the knapsack (without rotations). 2D Knapsack
admits a QPTAS [2] and a few constant approximation algorithms are known [19,
20, 29]. Here as well, finding a PTAS is a challenging open problem.

Bonsma et al. [6] established an intriguing connection between MISR and the
Unsplittable Flow on a Path problem. A PTAS for the latter problem was
recently obtained [24], closing a very long line of research (see, e.g., [3,
4, 5, 6, 25, 26]).

##  2 Preliminaries

In this paper, a (possibly closed) _curve_ is always assumed to be a polygonal
chain (or a singleton point) and a _polygon $S$_ is a bounded set with non-
empty interior $\operatorname{int}(S)$ and whose _boundary $\partial S$_ is a
closed curve. We denote the _closure of $S$_ as $\bar{S}$, so
$\bar{S}=\partial S\cup\operatorname{int}(S)$. We say that two polygons $S,T$
(with non-empty interior) _touch_ if
$\operatorname{int}(S)\cap\operatorname{int}(T)=\emptyset$ but $\partial
S\cap\partial T\neq\emptyset$ and _intersect_ if
$\operatorname{int}(S)\cap\operatorname{int}(T)\neq\emptyset$. A curve $f$
_touches_ $S$ if $f\cap\operatorname{int}(S)=\emptyset$ but $f\cap\partial
S\neq\emptyset$.

A line segment or curve is called _degenerate_ if it is a singleton point. A
line segment or curve is assumed to be non-degenerate unless we explicitly
state the opposite. For an (oriented) line segment $e=\overline{ww^{\prime}}$
(resp. curve $\gamma=w_{1}w_{2}\cdots w_{k}$) we define the _head of $e$ (of
$\gamma$)_ as $h(e)=w^{\prime}$ ($h(\gamma)=w_{k}$) and the _tail of $e$ (of
$\gamma$)_ as $t(e)=w$ ($t(\gamma)=w_{1}$) and the _interior of $e$ (of
$\gamma$)_ as $\operatorname{int}(e)=e\setminus\\{h(e),t(e)\\}$
($\operatorname{int}(\gamma)=\gamma\setminus\\{h(\gamma),t(\gamma)\\}$). For a
degenerate line segment (resp. curve), the head and the tail coincide with the
line segment (resp. curve).

For a vector $v=(x,y)$, let $v^{\perp}\coloneqq(y,-x)$ (which is $v$ rotated
clockwise orthogonally). For a positive integer $k$, let
$[k]\coloneqq\\{1,\dots,k\\}$.

Figure 1: A convex polygon in $4$ directions. The edge $e_{3}(P)$ is
degenerate.

Input. For a fixed positive integer $d$, the input of our problem is given by
a set of (pairwise linearly independent) _$d$ direction defining vectors_
$\mathcal{D}=\\{v_{1},\dots,v_{d}\\}\subseteq\mathbb{Z}^{2}$ and a set
$\mathcal{I}$ of $n$ convex polygons with edges oriented along the directions
given in $\mathcal{D}$. Polygons of this type are sometimes called _$d$
-discrete orientation polytopes ($d$-DOPs)_ [31]. In this paper, we will more
casually refer to them as (input) polygons; the significance of the word
“polygon” will be clear from context. Without loss of generality, assume
$v_{1}=(0,1)$ and that $v_{2},\dots,v_{d}$ point to the left and are ordered
by decreasing slope, see Figure 1. For $i\in\\{d+1,\dots,2d\\}$, let
$v_{i}\coloneqq-v_{i-d}$. The indices of the directions are counted modulo
$2d$, i.e., $i=i+2d=i-2d$. More explicitly, each polygon $P\in\mathcal{I}$ is
encoded by $2d$ integers $p_{1}(P),\dots,p_{2d}(P)$ as
$P=\\{x\in\mathbb{R}^{2}:\ x^{\intercal}v^{\perp}_{i}<p_{i}(P),\ \forall
i\in[2d]\\}$; and thus $\bar{P}=\\{x\in\mathbb{R}^{2}:\
x^{\intercal}v^{\perp}_{i}\leq p_{i}(P),\ \forall i\in[2d]\\}$. We assume that
those linear inequalities are all tight, including redundant ones111An
inequality is _redundant_ if we can remove it from the definition of $P$
without affecting $P$., i.e., $e_{i}(P)\coloneqq\bar{P}\cap\\{x:\
x^{\intercal}v^{\perp}_{i}=p_{i}(P)\\}\neq\emptyset$ for every $i\in[2d]$.
$e_{i}(P)$ is called the _edge of $P$ in direction $v_{i}$_. Then, for every
$i\in[2d]$, $e_{i}(P)$ and $e_{i+1}(P)$ are incident and
$h(e_{i}(P))=t(e_{i+1}(P))$. Note that $e_{1}(P)e_{2}(P)\cdots e_{2d}(P)$
forms a positively oriented closed curve.

Grid. Let $\mathcal{L}_{1}$ be the set of all lines in directions
$v_{1},\dots,v_{d}$ passing through the vertices of the input polygons. In
particular, all the edges (including the degenerate ones) of all the polygons
in the input lie on the lines in $\mathcal{L}_{1}$. Notice that
$|\mathcal{L}_{1}|\leq 2d^{2}n$. We recursively define $\mathcal{V}_{k}$, for
$k\in[2d]$ and $\mathcal{L}_{k}$, for $k\in\\{2,\dots,2d\\}$ as follows:
$\mathcal{V}_{k}$ is the set of intersection points of any two (non-parallel)
lines in $\mathcal{L}_{k}$, and $\mathcal{L}_{k}$ is the set of all lines in
directions $\mathcal{D}$ passing through points in $\mathcal{V}_{k-1}$. We
define the grid $\mathcal{G}_{k}=(\mathcal{L}_{k},\mathcal{V}_{k})$. Since
$|\mathcal{V}_{k}|\leq|\mathcal{L}_{k}|^{2}$ and
$|\mathcal{L}_{k}|\leq|\mathcal{V}_{k-1}|\cdot d$, it follows that
$|\mathcal{V}_{k}|\leq(2d^{3}n)^{2^{k}}$. The grid $\mathcal{G}_{2d}$ form the
coordinate system of our algorithm: every geometric object appearing in the
algorithm and the analysis lies on $\mathcal{G}_{2d}$. A line segment _$s$
lies on $\mathcal{G}_{k}$_ if $s$ lies on some line in $\mathcal{L}_{k}$ and
the extreme points of $s$ lie on $\mathcal{V}_{k}$. Similarly, a curve or
polygon lies on $\mathcal{G}_{k}$ if all of its line segments do so.

Container. Consider the grid $\mathcal{G}_{1}$. Let $C^{*}\in\mathcal{G}_{1}$
be a parallelogram that encloses all polygons in $\mathcal{I}$; we call
$C^{*}$ the _bounding box_.222It can, for example, be chosen as a
parallelogram delimited by the leftmost and rightmost vertical lines and the
top and bottom $v_{2}$-oriented lines in $\mathcal{G}_{1}$ (i.e., the
extension of $e_{2}(P^{\prime})$ where
$P^{\prime}=\operatorname*{arg\;max}_{P\in\mathcal{I}}p_{2}(P)$ and the
extension of $e_{d+2}(P^{\prime\prime})$ where
$P^{\prime\prime}=\operatorname*{arg\;max}_{P\in\mathcal{I}}p_{d+2}(P)$). A
_container_ (see Figure 2(a)) is a polygon on $\mathcal{G}_{2d}$ with
positively oriented boundary $s_{1}f_{1}s_{2}f_{2}\dots s_{\kappa}f_{\kappa}$
where $2\leq\kappa\leq 5$, such that:

  * •

$s_{1},s_{2},\dots,s_{\kappa}$ are disjoint and possibly degenerate _parallel_
line segments on $\mathcal{G}_{2d}$ (these will later be called _cutting
lines_).

  * •

For all $j\in[\kappa]$, $f_{j}$ is a simple curve on $\mathcal{G}_{2d}$
consisting of at most $2d+1$ line segments and $t(f_{j})=h(s_{j})$ and
$h(f_{j})=t(s_{j+1})$ for every $j\in[\kappa]$ (where $s_{\kappa+1}=s_{1}$).

  * •

For all $j\in[\kappa]$, $\operatorname{int}(s_{j})$ does not intersect with
any other part of the boundary of the container.

  * •

For all $i,j\in[\kappa],i\neq j$, the curves $f_{i}$ and $f_{j}$ might touch
but do not cross (defined below).

In particular, a container has at most $10d+10$ line segments. Let
$\mathcal{C}$ be the set of all containers $C$ with
$\operatorname{int}(C)\subseteq\operatorname{int}(C^{*})$. In particular,
$C^{*}$ is a container and $C^{*}\in\mathcal{C}$. A _bipartition of
$C\in\mathcal{C}$_ is a pair $\\{C_{1},C_{2}\\}\subseteq\mathcal{C}$ such that
$C_{1},C_{2}$ split up $C$, i.e., $\operatorname{int}(C)\setminus(\partial
C_{1}\cup\partial
C_{2})=\operatorname{int}(C_{1})\cup\operatorname{int}(C_{2})$ and $C_{1}$ and
$C_{2}$ may touch but not intersect.

Crossing curves. Two curves _cross_ (see also Figure 2(b)) if each one of them
contains a connected subcurve $w_{0}w_{1}\cdots w_{k}$ and $q_{0}q_{1}\cdots
q_{k}$, respectively, which form a _crossing_ , i.e., if $w_{0}\neq q_{0}$,
$w_{k}\neq q_{k}$, $w_{i}=q_{i}$ for $1\leq i\leq k-1$ and the (non-collinear)
triangles $w_{0}q_{0}w_{2}$ and $w_{t}q_{t}w_{t-2}$ have the same orientation
(i.e., are either both positively or both negatively oriented).333Any
container is thus _weakly simple_ according to the definitions in [14, Box
5.1] and [32]. The concept of weakly simple polygons is extensively discussed
in [11]. For two curves formed by at most $k$ line segments in total, it can
be decided in time $O(k^{3})$ whether there exists a crossing among them or
not [11]. With this definition, it is guaranteed that every container has a
well-defined interior [11].

(a)

(b)

Figure 2: A container with $\kappa=5$. An illustration of crossing and non-
crossing.

##  3 Our Approach

First, we present the algorithm in Section 3.1, and give an overview of the
analysis in Sections 3.2 and 3.3. The detailed analysis and proofs are given
in the later sections.

###  3.1 The algorithm

Our algorithm is a dynamic program that generalizes the algorithm in [21].
Each cell of the dynamic program corresponds to a container $C\in\mathcal{C}$.
For each container, the dynamic program computes a set of disjoint polygons
$\operatorname{Dyn}(C)\subseteq\mathcal{I}$ as follows. If $C$ encloses no
polygon in $\mathcal{I}$, set $\operatorname{Dyn}(C)=\emptyset$. If $C$
encloses exactly one polygon $P\in\mathcal{I}$, set
$\operatorname{Dyn}(C)=\\{P\\}$. Otherwise, the dynamic program goes through
all bipartitions of $C$ and chooses the bipartition $\\{C_{1},C_{2}\\}$ that
maximizes $|\operatorname{Dyn}(C_{1})|+|\operatorname{Dyn}(C_{2})|$ and sets
$\operatorname{Dyn}(C)=\operatorname{Dyn}(C_{1})\cup\operatorname{Dyn}(C_{2})$.
The final output of the algorithm is $\operatorname{Dyn}(C^{*})$.

######  Lemma 3.1 (Running time).

Let $N=|\mathcal{V}_{2d}|$ be the number of points in the grid
$\mathcal{G}_{2d}$. $\operatorname{Dyn}(C^{*})$ can be computed in time
$O\big{(}N^{20d+20}\big{)}=O((nd)^{O(d4^{d})})$.

######  Proof 3.2.

The boundary of each container can be identified by a sequence of $10d+10$
line segments in $\mathcal{G}_{2d}$. There are therefore at most
$O\big{(}N^{10d+10}\big{)}$ containers in $\mathcal{C}$. As argued in [21],
any bipartition $\\{C_{1},C_{2}\\}$ of $\mathcal{C}$ is determined by the
boundary between $C_{1}$ and $C_{2}$, i.e., $\partial C_{1}\cap\partial
C_{2}$, which is composed of at most $10d+10$ line segments. Thus, to compute
$\operatorname{Dyn}(C)$, the dynamic program does not consider more that
$O\big{(}N^{10d+10}\big{)}$ bipartitions. This gives a total running time
$O\big{(}N^{20d+20}\big{)}$. The lemma follows since $N=O((2d^{3}n)^{4^{d}})$,
see Section 2.

It is not hard to see that the output $\operatorname{Dyn}(C^{*})$ is indeed an
independent set, so we will focus on showing that the algorithm has the
claimed approximation guarantee.

###  3.2 Analysis

By construction, the output solution $\operatorname{Dyn}(C^{*})$ is the union
of the solutions of two smaller containers, and so on. We represent this
structure by a binary tree called _recursive partition_ defined below. We
argue that $\operatorname{Dyn}(C^{*})$ is the best solution among all the
solutions representable by a recursive partition. Then, we show the existence
of a recursive partition that respects the approximation factor claimed in
Theorem 1.1.

######  Definition 3.3.

For a set $\mathcal{R}\subseteq\mathcal{I}$, a _recursive partition_ of
$\mathcal{R}$ is a rooted tree $T$ with vertex set $V$ such that

  * •

every node $u\in V$ corresponds to a pair $(C_{u},\operatorname{Pr}(C_{u}))$
where $C_{u}\in\mathcal{C}$ is a container, and $\operatorname{Pr}(C_{u})$ is
the set of _protected_ polygons of $\mathcal{R}$ contained in $C_{u}$,

  * •

the root $r$ of $T$ corresponds to $(C^{*},\emptyset)$, i.e., $C_{r}=C^{*}$
and $\operatorname{Pr}(C_{r})=\emptyset$;

  * •

every internal node has two children $u_{1},u_{2}$ such that: $C_{u_{1}}$ and
$C_{u_{2}}$ form a bipartition of $C_{u}$, and
$\operatorname{Pr}(C_{u})\subseteq\operatorname{Pr}(C_{u_{1}})\cup\operatorname{Pr}(C_{u_{2}})$;

  * •

for every leaf $u$ of $T$, $C_{u}$ contains exactly one polygon
$P_{u}\in\mathcal{R}$ or no polygon in $\mathcal{R}$ at all;

  * •

for every $P\in\mathcal{R}$, there exists a leaf $u$ of $T$ such that $P$ lies
in $C_{u}$.

Clearly, if $\mathcal{R}\subseteq\mathcal{I}$ admits a recursive partition, it
must be an independent set. It is easy to show by induction on the height of
the tree that the output $\operatorname{Dyn}(C^{*})$ admits a recursive
partition, which leads to the following lemma.

######  Lemma 3.4 ([21, Lemma 2.2]).

If $\mathcal{R}\subseteq\mathcal{I}$ admits a recursive partition, then
$|\operatorname{Dyn}(C^{*})|\geq|\mathcal{R}|$.

Therefore, Theorem 1.1 is a consequence of Lemma 3.1 and the following
proposition.

######  Proposition 3.5.

Let $\operatorname{OPT}$ be an optimal solution of an instance of MISP. There
exists a recursive partition for some set
$\mathcal{R}\subseteq\operatorname{OPT}$ such that
$|\mathcal{R}|\geq\frac{3}{8d}|\operatorname{OPT}|$.

###  3.3 Informal overview of the proof of Proposition 3.5

Intuitively, we construct the set $\mathcal{R}$ by starting from an optimal
solution $\operatorname{OPT}$ contained in the initial container (the bounding
box) $C_{r}=C^{*}$ and $\operatorname{Pr}(C_{r})=\emptyset$. Then, we will
recursively partition the current container $C_{u}$ into two containers
$C_{u_{1}}$ and $C_{u_{2}}$. $\mathcal{R}$ is then defined as the set of
polygons of $\operatorname{OPT}$ that are fully contained in the leaf
containers. For a polygon $P$ in $C_{u}$, we say that $P$ is _lost (at
$C_{u}$)_ if it is neither contained in $C_{u_{1}}$ nor in $C_{u_{2}}$.

Below, one of the $d$ directions in $\mathcal{D}$ plays a special role:
without loss of generality, we assume that this direction is
vertical/vertical-up ($v_{1}$). The exact choice will be made later.

Accountable polygons. We prove that there exists a subset
$\operatorname{ACC}\subseteq\operatorname{OPT}$ (the _accountable_ polygons)
with at least $\frac{3}{4d}|\operatorname{OPT}|$ polygons, such that for each
polygon $P\in\operatorname{ACC}$ lost during partitioning of some $C_{u}$ into
$C_{u_{1}}$ and $C_{u_{2}}$ we can _charge_ a unique polygon
$P^{\prime}\in\operatorname{OPT}$ and $P^{\prime}$ lies in a leaf container of
the recursive partition.

We next describe in more details the set of accountable polygons
$\operatorname{ACC}$ and how protected polygons are defined. For technical
reasons, we replace each original polygon $P\in\operatorname{OPT}$ with a new
polygon $\operatorname{ext}(P)$ lying on $\mathcal{G}_{2d}$ that contains $P$
(see Figures 3 and 4). The new set of polygons remains independent, and we
will simply denote it by $\operatorname{OPT}$ in the following.

Let $P\in\operatorname{OPT}$ and consider its edge $e_{1}(P)$ in direction
vertical-up. Let $P^{\prime}\in\operatorname{OPT}$ and consider its edge
$e_{d+1}(P^{\prime})$ in direction vertical-down. We say that $P$ _sees_
$P^{\prime}$ if $e_{1}(P)$ is non-degenerate and
$h(e_{d+1}(P^{\prime}))\in\operatorname{int}(e_{1}(P))\cup\\{t(e_{1}(P))\\}$,
see Figure 4. We let the set $\operatorname{ACC}$ of accountable polygons be
the polygons $P\in\operatorname{OPT}$ such that $P$ sees some
$P^{\prime}\in\operatorname{OPT}$.

It is easy to show that each polygon is seen by at most one other polygon in
$\operatorname{OPT}$.

Partitioning. For $C\in\mathcal{C}$, let $\operatorname{OPT}(C)$ be the set of
polygons in $\operatorname{OPT}$ that lie on $\operatorname{int}(C)$. Our
construction is guided by a partitioning lemma which is stated later. Roughly
speaking, let $C$ be a container with $|\operatorname{OPT}(C)|\geq 2$, and let
$\operatorname{Pr}(C)$ be the set of protected polygons in $C$. The
partitioning lemma states that $C$ can be bipartitioned by a curve $\Gamma$
into two smaller containers $C_{1}$ and $C_{2}$ such that

  1. (P1)

$\Gamma$ contains a vertical line segment $\ell$ that intersects all the
polygons in $\operatorname{OPT}(C)$ that are intersected by $\Gamma$.

  2. (P2)

$\Gamma$ does not intersect any polygon in $\operatorname{Pr}(C)$,

  3. (P3)

$\operatorname{Pr}(C)\subseteq\operatorname{Pr}(C_{1})\cup\operatorname{Pr}(C_{2})$.

We stress that the lemma does _not_ hold for an arbitrary set
$\operatorname{Pr}(C)$ (e.g., if we take
$\operatorname{Pr}(C)=\operatorname{OPT}(C)$). The set of _protected_ polygons
in a container is defined below.

Charging and protecting. The recursive partition which determines
$\mathcal{R}$ is defined by repeatedly applying the partitioning lemma. During
the construction of the recursive partition, we need to guarantee that the
vertical line segments given by (P1) do not intersect too many polygons from
$\operatorname{OPT}$; this is the only possibility of “losing” some polygons.
For this, we use the set of accountable polygons
$\operatorname{ACC}\subseteq\operatorname{OPT}$. Whenever we apply the
partitioning lemma, the line $\ell$ intersects some polygons in
$\operatorname{ACC}$. For each $P\in\operatorname{ACC}$ that is intersected by
$\ell$, i.e., for each lost polygon $P\in\operatorname{ACC}$, we charge
exactly one polygon $P^{\prime}$ seen by $P$. By (P1), if $\ell$ intersects
$P$, then $\Gamma$ does not intersect $P^{\prime}$. If $P^{\prime}$ is not
already an element of $\operatorname{Pr}(C)$ and thus an element of
$\operatorname{Pr}(C_{1})\cup\operatorname{Pr}(C_{2})$, then we add the
polygon $P^{\prime}$ to either $\operatorname{Pr}(C_{1})$ if $P^{\prime}\in
C_{1}$ or to $\operatorname{Pr}(C_{2})$ if $P^{\prime}\in C_{2}$. Moreover, if
there is a polygon $P^{\prime\prime}\in\operatorname{OPT}(C)$ that sees $P$,
then $P^{\prime\prime}$ is also added to either $\operatorname{Pr}(C_{1})$ or
$\operatorname{Pr}(C_{2})$.

By (P3), adding $P^{\prime}$ to one of $\operatorname{Pr}(C_{1})$ and
$\operatorname{Pr}(C_{2})$ means that the charged polygon $P^{\prime}$ will
remain protected. By (P2), $P^{\prime}$ will not be intersected by the curves
in the following applications of the partitioning lemma. Therefore
$P^{\prime}$ will be an element in $\mathcal{R}$ (our intended recursive
partition). Adding $P^{\prime\prime}$ to one of $\operatorname{Pr}(C_{1})$ and
$\operatorname{Pr}(C_{2})$ is also necessary, because the polygon $P$ is
already lost and if we were to lose $P^{\prime\prime}$ in one of the following
steps, there might not be a polygon which we could charge the loss of
$P^{\prime\prime}$ to.

We conclude that for every polygon $P\in\operatorname{ACC}$ lost in the
partitioning of a container, we can guarantee that a unique polygon
$P^{\prime}$ seen by $P$ is charged, and it will become the protected polygon
in a leaf. At least half of the polygons in $\operatorname{ACC}$ are either
lost or not, so there are at least $\frac{1}{2}|\operatorname{ACC}|$ polygons
in the leaves. 3.5 follows since
$|\operatorname{ACC}|\geq\frac{3}{4d}|\operatorname{OPT}|$.

###  3.4 Comparison with previous work on MISR

Overall, we follow the same high level approach as the papers on MISR [21, 22,
37]. Yet, to generalize the results on MISR to MISP, we encounter several
technical difficulties. We discuss a few of the more prominent ones below.

To define the set $\operatorname{ACC}$, we need the following property (later
referred as (E3)): for every $P\in\operatorname{OPT}$ and every non-degenerate
edge $e$ of $P$, $\operatorname{int}(e)$ touches either another polygon
$P^{\prime}\in\operatorname{OPT}$ or the boundary of the bounding box. This
property can be obtained by “maximally extending” $\operatorname{OPT}$ as in
[21, 37]. The difficulty here, unlike in the case of rectangles, is that
naively extending the polygons can result in a grid of exponential size in
$n$.

For MISR [21, 37], the accountable polygons correspond to the non-nested
polygons (both vertical and horizontal). It is essentially trivial to show
that the number of non-nested rectangles is at least half of the optimal
number of rectangles. In case of convex polygons, we require a more careful
argument to show that there are at least $\frac{3}{4d}|\operatorname{OPT}|$
accountable polygons.

To obtain the partitioning lemma, we follow the same idea as in the case of
axis-parallel rectangles but we need to work with significantly more complex
objects. Firstly, the containers we work with have $O(d)$-times more line
segments. Secondly, the containers that appear in our construction might not
be simple (since some parts of the boundary may touch other parts of the
boundary). These difficulties require more elaborate and more technical
arguments.

##  4 Charging options and accountable polygons

Like the papers [21, 37] on MISR, first, we extend an optimum solution
$\operatorname{OPT}$.

######  Definition 4.1.

Let $\operatorname{OPT}$ be an optimal solution of a MISP instance. We say
that $\operatorname{OPT}^{\prime}$ is a _maximal extension_ of
$\operatorname{OPT}$ if:

  1. (E1)

$\operatorname{OPT}^{\prime}$ is an independent set of (convex) polygons on
$\mathcal{G}_{2d}$ and enclosed in $C^{*}$.

  2. (E2)

There exists a bijection
$\operatorname{ext}:\operatorname{OPT}\to\operatorname{OPT}^{\prime}$ such
that $P\subseteq\operatorname{ext}(P)$ for every $P\in\operatorname{OPT}$.

  3. (E3)

For every $P\in\operatorname{OPT}^{\prime}$ and every non-degenerate edge $e$
of $P$, $\operatorname{int}(e)$ touches either another polygon
$P^{\prime}\in\operatorname{OPT}^{\prime}$ or $\partial C^{*}$.

In Appendix A, we show that a maximal extension of $\operatorname{OPT}$
exists. The idea is to start with $\operatorname{OPT}$ and whenever some non-
degenerate edge $e$ of a polygon $P$ does not satisfy (E3), then we extend the
polygon $P$ by moving the edge $e$ “outside”, see Figure 3. We show that if we
extend all the edges of the same direction not satisfying (E3) together, then
the maximal extension lies on the grid $\mathcal{G}_{2d}$.

By (E2) and (E1), it suffices to prove 3.5 for a maximal extension of
$\operatorname{OPT}$. (In particular, (E1) implies that the polygons in
$\operatorname{OPT}^{\prime}$ have edges in the given $d$ directions.) The
purpose of a maximal extension is (E3), which is helpful to bound the number
of accountable polygons. For the rest of the paper, we assume that
$\operatorname{OPT}$ is already “maximally extended” and thus satisfies (E3),
and we work with the grid $\mathcal{G}_{2d}$.

Figure 3: Illustration of the process of extending a polygon $P$. We extend
$P$ by moving the edge $e$ of $P$ until $\operatorname{int}(e)$ touches
another polygon in $\operatorname{OPT}$.

Figure 4:  A black arrow from $P$ to $P^{\prime}$ indicates that $P$ sees
$P^{\prime}$ with respect to the option $(v_{1},t)$, i.e., direction vertical-
up and tail. The blue (resp. red) corners represent the tails (resp. head) of
all edges with direction vertical-down ($v_{5}$). Thus, a polygon $P$ sees a
polygon $P^{\prime}$ if the vertical-up edge of $P$ is touching the red corner
of $P^{\prime}$.

In the rest of this section, by the term _direction_ we mean a direction
$v_{i}$ where $i\in[2d]$, and say that edge $e$ is of direction $v_{i}$ if the
points of the edge $e$ correspond to $t(e)+\lambda\cdot v_{i}$, with
$\lambda\geq 0$. A _charging option_ is specified by a direction $v_{i}$,
$i\in[2d]$ and a choice between $t$ and $h$. Let
$\mathcal{O}=\\{v_{i}\\}_{i\in[2d]}\times\\{t,h\\}$ be the set of the $2d\cdot
2=4d$ charging options. We show the existence of a charging option and a
subset $\operatorname{ACC}\subseteq\operatorname{OPT}$ of accountable polygons
with respect to this option such that (essentially)
$|\operatorname{ACC}|\geq\frac{3}{4d}|\operatorname{OPT}|$.

######  Definition 4.2.

Let $P\in\operatorname{OPT}$ and let $e$ be the edge of $P$ in direction
$v=v_{i}$, $i\in[2d]$.

  * •

Let $P^{\prime}\in\operatorname{OPT}$ and $e^{\prime}$ be the (possibly
degenerate) edge of $P^{\prime}$ of direction $-v$. For $a\in\\{t,h\\}$, we
say that $P$ _sees $P^{\prime}$ with respect to $(v,a)$_ if $e$ is non-
degenerate and if $\neg a(e^{\prime})\in\operatorname{int}(e)\cup\\{a(e)\\}$,
where $\neg t=h$ and $\neg h=t$. (See Figure 4.)

  * •

Whenever there exists $P^{\prime}\in\operatorname{OPT}$ and a charging option
$(v,a)$, such that $P$ sees $P^{\prime}$ for $(v,a)$ then we say that $P$ is
_accountable for $(v,a)$_.

######  Lemma 4.3.

Let $(v,a)\in\mathcal{O}$ be a charging option. Any polygon
$P^{\prime}\in\operatorname{OPT}$ is seen by at most one other polygon
$P\in\operatorname{OPT}$ with respect to $(v,a)$.

######  Proof 4.4.

Assume that $P^{\prime}$ is seen by $P_{1},P_{2}\in\operatorname{OPT}$ with
respect to $(v,a)$. Let $e_{1}$ and $e_{2}$ be the edge in direction $v$ of
$P_{1}$ and $P_{2}$, respectively. Then we have $\neg
a(e^{\prime})\in(\operatorname{int}(e_{1})\cup\\{a(e_{1})\\})\cap(\operatorname{int}(e_{2})\cup\\{a(e_{2})\\})$.
Since $\operatorname{int}(e_{1})\neq\emptyset$ and
$\operatorname{int}(e_{2})\neq\emptyset$, it follows that
$\operatorname{int}(e_{1})\cap\operatorname{int}(e_{2})\neq\emptyset$. This
implies that $P_{1}$ and $P_{2}$ intersect, thus $P_{1}=P_{2}$.

We say that a polygon $P\in\operatorname{OPT}$ is a _corner polygon_ in the
bounding box $C^{*}$, if all but one of the edges of $P$ are contained in the
boundary of $C^{*}$. In particular, $P$ is a corner polygon if $P=C^{*}$.
Similarly, if $C^{*}$ is partitioned into two convex polygons, then both are
corner polygons. Let $Z\subseteq\operatorname{OPT}$ be the set of corner
polygons in $C^{*}$. Since $C^{*}$ is a parallelogram, we have $|Z|\leq 4$,
and the polygon $C^{\prime}=C^{*}\setminus(\bigcup Z)$ is convex.

######  Lemma 4.5 (Good charging option).

Assume that $\operatorname{OPT}$ satisfies (E3). Then, there exists a charging
option $(v,a)\in\mathcal{O}$ such that at least
$\frac{3}{4d}|\operatorname{OPT}\setminus Z|$ polygons in
$\operatorname{OPT}\setminus Z$ are accountable with respect to $(v,a)$.

######  Proof 4.6.

Let $P\in\operatorname{OPT}$ and $c$ be a vertex of $P$. Let $e,e^{\prime}$ be
the two non-degenerate edges incident to $c$ where $c=h(e)=t(e^{\prime})$.
Denote with $v$ (resp. $v^{\prime}$) the direction of $e$ (resp.
$e^{\prime}$).

######  Claim 1.

Suppose that $e$ or $e^{\prime}$ (or both) does not lie on the boundary of
$C^{*}$. Then, $P$ is accountable with respect to $(v,h)$ or $(v^{\prime},t)$.

By (E3), each non-degenerate edge of $P$ not contained in the boundary of the
bounding box, must touch some other polygon of $\operatorname{OPT}$ in its
interior. By assumption either $e$ or $e^{\prime}$ does not lie on the
boundary of $C^{*}$, without loss of generality, say $e$. Then $P$ touches
some $P_{1}\in\operatorname{OPT}$ on $\operatorname{int}(e)$, i.e.,
$\operatorname{int}(e)\cap e_{1}\neq\emptyset$, where $e_{1}$ is the edge of
$P_{1}$ in direction $-v$ ($e_{1}$ could be degenerate). See Figure 5. If $P$
sees $P_{1}$ with respect to $(v,h)$, i.e.,
$t(e_{1})\in\operatorname{int}(e)\cup\\{h(e)\\}$ then the claim is true, so
assume that $t(e_{1})\notin\operatorname{int}(e)\cup\\{h(e)\\}$. This however
implies $c\in\operatorname{int}(e_{1})$.

Since $c\in\operatorname{int}(e_{1})$ and $C^{*}$ is convex, it follows that
$e^{\prime}$ is not on the boundary of $C^{*}$. Then, by (E3), there exists
$P_{2}\in\operatorname{OPT}$ that touches $P$ on
$\operatorname{int}(e^{\prime})$, i.e., $\operatorname{int}(e^{\prime})\cap
e_{2}\neq\emptyset$, where $e_{2}$ is the edge of $P_{2}$ in direction
$-v^{\prime}$. If $P$ does not see $P_{2}$ with respect to $(v^{\prime},t)$,
then $c\in\operatorname{int}(e_{2})$ by the same argument as before. So
$\operatorname{int}(e_{1})$ and $\operatorname{int}(e_{2})$ intersect in $c$
and thus $P_{1}$ and $P_{2}$ intersect (as $e_{1}$ and $e_{2}$ have different
direction) which is a contradiction. Therefore, $P$ must see $P_{2}$ with
respect to $(v^{\prime},t)$.

Figure 5: Claim 1: the blue (red) corners represents the tail (head) of the
edges in direction $-v$.

Consider $P\in\operatorname{OPT}\setminus Z$. Since $P$ is not a corner
polygon in $C^{*}$, it has at least two consecutive non-degenerate edges such
that neither of them lies on $\partial C^{*}$. By Claim 1, every vertex of $P$
incident to one or both of these edges, provides a charging option for which
$P$ is accountable. Thus, the total number of pairs $(P,(v,a))$ with
$P\in\operatorname{OPT}\setminus Z$ and $(v,a)\in\mathcal{O}$ such that $P$ is
accountable with respect to $(v,a)$ is at least $3|\operatorname{OPT}\setminus
Z|$. Since $|\mathcal{O}|=4d$, there exists an option $(v,a)$ for which the
number of accountable polygons in $\operatorname{OPT}\setminus Z$ is at least
$\frac{3}{4d}|\operatorname{OPT}\setminus Z|$.444If we could guarantee a
maximal extension in which all the polygons have at least $4$ sides, then we
would improve $\frac{3}{4d}$ to $\frac{1}{d}$. In particular, when $d=2$ we
are in the case of axis-parallel rectangles and we obtain a
$2d=4$-approximation algorithm. This is the same approximation factor achieved
in [21, 22, 37] by charging each lost rectangle to one protected rectangle
(the improved $2+\epsilon$ factor requires a more complex charging).

##  5 Recursive partitioning

Without loss of generality (by rotating and mirroring the initial instance if
necessary), we assume that the option $(v,a)$ satisfying Lemma 4.5 is
vertical-up and tail, i.e., $(v_{1},t)$. In other words, for any
$P\in\operatorname{OPT}$, if $e_{1}(P)$ is non-degenerate and if there is a
$P^{\prime}\in\operatorname{OPT}$ such that
$h(e_{d+1}(P^{\prime}))\in\operatorname{int}(e_{1}(P))\cup t(e_{1}(P))$, then
we say that _$P$ sees $P^{\prime}$_ (and _$P^{\prime}$ is seen by $P$_) and
that $P$ is _accountable_. Lemma 4.5 states that there exists a subset
$\operatorname{ACC}\subseteq\operatorname{OPT}\setminus Z$ of accountable
polygons such that
$|\operatorname{ACC}|\geq\frac{3}{4d}|\operatorname{OPT}\setminus Z|$,
consequently $|Z|+|\operatorname{ACC}|\geq\frac{3}{4d}|\operatorname{OPT}|$.

We will construct a recursive partition for a specific subset
$\mathcal{R}\subseteq\operatorname{OPT}$, such that
$|\mathcal{R}|\geq|Z|+\frac{1}{2}|\operatorname{ACC}|$, which proves 3.5.
Recall that $\operatorname{OPT}(C)$ denotes the set of polygons in
$\operatorname{OPT}$ that lie on $\operatorname{int}(C)$. Moreover, all of the
polygons in $\operatorname{OPT}$ and the bounding box $C^{*}$ lie on the grid
$\mathcal{G}_{2d}$.

Handling corner polygons. If $Z\neq\emptyset$, then we construct the first few
nodes of the recursive partition as follows. Take any corner polygon $P\in Z$.
Recall that the root $r$ of the recursive partition corresponds to
$(C^{*},\emptyset)$. We add two children $u_{1},u_{2}$ to $r$ and partition
$C^{*}$ into the containers $C_{u_{1}}=P$ and $C_{u_{2}}=C^{*}\setminus P$.
Set $\operatorname{Pr}(C_{u_{1}}),\operatorname{Pr}(C_{u_{2}})=\emptyset$. By
construction, $\operatorname{OPT}(C_{u_{1}})=\\{P\\}$ (so $u_{1}$ is a leaf in
the final tree and
$\operatorname{OPT}(C_{u_{2}})=\operatorname{OPT}\setminus\\{P\\}$. Notice
that $C^{*}\setminus P$ is convex with at most five line segments since
$C^{*}$ is convex. $C^{*}\setminus P$ has five line segments if $P$ is a
triangle, and less if $P$ has more than three sides.) We recurse by treating
$C_{u_{2}}$ as the new bounding box.

We end up with a tree on $|Z|+1$ leaves, where for one leaf $u$, $C_{u}$ is a
convex polygon such that
$\operatorname{OPT}(C_{u})=\operatorname{OPT}\setminus Z$ and with at most
eight line segments (since $|Z|\leq 4$) and
$\operatorname{Pr}(C_{u})=\emptyset$. Each of the remaining $|Z|$ leaves
coincides with a unique element in $Z$. Thus, it suffices to construct the
recursive partition of $\operatorname{OPT}\setminus Z$ by treating $C_{u}$ as
the bounding box with at most $8$ line segments. Equivalently, we assume
$Z=\emptyset$ and allow $C^{*}$ to have up to eight line segments for the rest
of this paper.

###  5.1 The partitioning lemma – formal statement

For any $P\in\operatorname{OPT}$, let the _top of_ $P$ be defined as the curve
$\operatorname{top}(P)=e_{2}(P)e_{3}(P)\cdots e_{d}(P)$ and the _bottom of
$P$_ as the curve $\operatorname{bot}(P)=e_{d+2}(P)e_{d+3}(P)\cdots
e_{2d}(P)$. We define the bottom and top of the bounding box $C^{*}$ in the
same way. The following definitions are illustrated in Figure 6.

######  Definition 5.1 (Top and bottom fences).

Let $P,P^{\prime}\in\operatorname{OPT}$ be two polygons such that $P$ sees
$P^{\prime}$. A _top-fence_ is (a segment of) the curve
$\operatorname{top}(P)\overline{h(e_{1}(P))t(e_{d+1}(P^{\prime}))}\operatorname{top}(P^{\prime})$
such that the first and last line segment is not vertical. Symmetrically, a
_bottom-fence_ is (a segment of) the curve
$\operatorname{bot}(P)\overline{t(e_{1}(P))h(e_{d+1}(P^{\prime}))}\operatorname{bot}(P^{\prime})$
such that the first and last line segment is not vertical.

If $P\in\operatorname{OPT}$ does not see any polygon, then a segment of its
bottom (or top) is also called a bottom-fence (resp. top-fence).

For a vertical line segment (cutting line) $s$, we say that a fence _emerges
from $s$_ if one extreme point of the fence lies on $s$.

To prove the partitioning lemma, we further specialize the definition of a
container (see Section 2)

######  Definition 5.2 (Structured container).

A container $C$ with $\partial C=s_{1}f_{1}s_{2}f_{2}\cdots
s_{\kappa}f_{\kappa}$, $\kappa\leq 5$, is _structured_ if the _cutting lines_
$s_{1},\dots,s_{\kappa}$ are vertical and the curves $f_{1},\dots,f_{\kappa}$
are fences.

We say that a cutting line is a _left cutting line_ if it is oriented
downwards (or degenerate), and _right cutting line_ if it is oriented upwards
(or degenerate). In a structured container, the left cutting lines (and thus
right cutting lines) are consecutive (e.g., $s_{1},\dots,s_{\kappa^{\prime}}$
are left and $s_{\kappa^{\prime}+1},\dots,s_{\kappa}$ are right cutting lines
for some $\kappa^{\prime}\in[\kappa-1]$).

######  Definition 5.3 (Protected by fences).

Let $C$ be a structured container and $s$ be a (possibly degenerate) cutting
line on $C$. We say that a polygon $P\in\operatorname{OPT}(C)$ is _protected
from the left in $C$ via $s$_ if $s$ is a left cutting line on $\partial C$
and

  * •

there exists a top-fence $\gamma_{h}$ in $C$ emerging from $s$, ending in
$h(e_{1}(P))$, and with $\operatorname{top}(P)\subseteq\gamma_{h}$, and

  * •

there exists a bottom-fence $\gamma_{t}$ in $C$ emerging from $s$, ending in
$t(e_{1}(P))$, and with $\operatorname{bot}(P)\subseteq\gamma_{t}$.

We say that $P$ is protected by fences _$\gamma_{h}$ and $\gamma_{t}$_.
Symmetrically, we say that a polygon $P\in\operatorname{OPT}(C)$ is _protected
from the right in $C$ via $s$_ if $s$ is a right cutting line on $\partial C$
and

  * •

there exists a top-fence $\sigma_{h}$ in $C$ emerging from $s$, ending in
$t(e_{d+1}(P))$, and with $\operatorname{top}(P)\subseteq\sigma_{h}$, and

  * •

there exists a bottom-fence $\sigma_{t}$ in $C$ emerging from $s$, ending in
$h(e_{d+1}(P))$, and with $\operatorname{bot}(P)\subseteq\sigma_{t}$.

We say that _$P$ is protected by fences $\sigma_{h}$ and $\sigma_{t}$._ A
polygon $P\in\operatorname{OPT}(C)$ is _protected by fences in $C$_ if it is
either protected from the left in $C$ or protected from the right in $C$.

Figure 6: Example of a structured container with $\kappa=4$. The black arrows
represent “seeing”, top-fences are green, bottom-fences are blue. The polygons
$P_{1},P_{3},P_{4},P_{5},P_{8}$ are protected (only) from the left,
$P_{14},P_{16}$ are protected (only) from the right, $P_{9},P_{11}$ are
protected both from the left and from the right. Notice that the fences that
protect $P_{14}$ (from the right) are not unique since $P_{14}$ sees $P_{15}$
and $P_{16}$ which are cut and touch $s_{4}$, respectively. Note also that the
bottom-fences touching $P_{8},P_{11}$ and $P_{11},P_{13}$ overlap.

We will show that each polygon in $\operatorname{Pr}(C)$ appearing in the
construction of the recursive partition can be protected _by fences_ in $C$.

Next, we state the partitioning lemma, the proof is presented in Appendix B.
The lemma holds only for _structured_ containers. This matters for the
construction of the recursive partition but it does not affect the algorithm,
as it considers all possible containers.

######  Lemma 5.4 (Partitioning lemma).

Let $C$ be a structured container such that $|\operatorname{OPT}(C)|\geq 2$,
and let $\cal P$ be a set of polygons in $C$ protected by fences. Then, there
exists a curve $\Gamma$ such that

  1. (P1)

$\Gamma$ partitions $C$ into two structured containers
$C_{1},C_{2}\in\mathcal{C}$ with non-empty interiors.

  2. (P2)

All the polygons in $\operatorname{OPT}(C)$ that are intersected by $\Gamma$
are intersected by one vertical cutting line $\ell\subseteq\Gamma$.

  3. (P3)

$\Gamma$ does not intersect any polygon protected by fences.

  4. (P4)

Any polygon protected by fences in $C$ is protected by fences in either
$C_{1}$ or $C_{2}$.

###  5.2 Construction and analysis of the recursive partition

In this section we prove 3.5, i.e., we provide a recursive partition for
$\mathcal{R}\subseteq\operatorname{OPT}$ with
$|\mathcal{R}|\geq\frac{1}{2}|\operatorname{ACC}|$. (Recall that we already
argued that we can assume $Z=\emptyset$.) We give an iterative construction of
a recursive partition with the help of the partitioning lemma.

We initialize a tree $T$ with root node $r$, $C_{r}=C^{*}$, and
$\operatorname{Pr}(C_{r})=\emptyset$. Then, iteratively, for every childless
node $u\in V(T)$ with $|\operatorname{OPT}(C_{u})|\geq 2$, add two children
$u_{1},u_{2}$ to $u$ and choose $C_{u_{1}},C_{u_{2}}\in\mathcal{C}$ as
provided by (P1) in the partitioning lemma applied to $C_{u}$ and
$\operatorname{Pr}(C_{u})$. Define the set of protected polygons
$\operatorname{Pr}(C_{u_{1}})$ and $\operatorname{Pr}(C_{u_{1}})$ as follows.

  1. (A1)

Set
$\operatorname{Pr}(C_{u_{1}})=\operatorname{Pr}(C_{u})\cap\operatorname{OPT}(C_{u_{1}})$
and
$\operatorname{Pr}(C_{u_{1}})=\operatorname{Pr}(C_{u})\cap\operatorname{OPT}(C_{u_{1}})$.

  2. (A2)

For each $P\in\operatorname{ACC}$ that is intersected by $\ell$, i.e., each
$P\in\operatorname{ACC}$ that is lost, if $P$ sees a polygon
$P^{\prime}\in\operatorname{OPT}(C_{u})$ (if $P$ sees more than one polygon in
$\operatorname{OPT}(C_{u})$, choose one of them arbitrarily), add $P^{\prime}$
to $\operatorname{Pr}(C_{u_{1}})$ if $P^{\prime}$ is in $C_{u_{1}}$ or to
$\operatorname{Pr}(C_{u_{2}})$ if $P^{\prime}$ is in $C_{u_{2}}$. Moreover,
charge the loss of $P$ to $P^{\prime}$.

  3. (A3)

For each $Q^{\prime}\in\operatorname{OPT}(C_{u})$ intersected by $\ell$ for
which there is a polygon $Q\in\operatorname{OPT}(C_{u})$ that sees
$Q^{\prime}$, add $Q$ to either $\operatorname{Pr}(C_{u_{1}})$ or
$\operatorname{Pr}(C_{u_{2}})$ depending whether $Q$ is in $C_{u_{1}}$ or
$C_{u_{2}}$.

We first show to that by this construction, a polygon is protected only if it
is protected by fences.

######  Lemma 5.5.

Let $P^{\prime}\in\operatorname{Pr}(C_{u})$ for a node $u$ of $T$. There exist
fences that protect $P^{\prime}$ in $C_{u}$.

######  Proof 5.6.

We first argue in the case that $P^{\prime}$ is protected for the first time,
i.e., added to $\operatorname{Pr}(C_{u})$ via (A2) or (A3). Let $u^{\prime}$
be the parent of $u$ in $T$.

First assume that $P^{\prime}$ is protected via (A2). Let
$P\in\operatorname{ACC}\cap\operatorname{OPT}(C_{u^{\prime}})$ be the polygon
that sees $P^{\prime}$. By definition, $P$ is intersected by the cutting line
$\ell_{u^{\prime}}$ from (P1) during the bipartitioning of $C_{u^{\prime}}$
Let $p_{x}$ and $p_{y}$ be the two intersection points of $\ell_{u^{\prime}}$
and $\partial P$, where $p_{x}$ is above $p_{y}$, see Figure 7. Since $P$ sees
$P^{\prime}$, the curve $\gamma_{x}$ on $\operatorname{top}(P)$ and
$\operatorname{top}(P^{\prime})$ from $p_{x}$ to $h(e_{1}(P^{\prime}))$ is a
top-fence and the curve $\gamma_{y}$ on $\operatorname{bot}(P)$ and
$\operatorname{bot}(P^{\prime})$ from $p_{y}$ to $t(e_{1}(P^{\prime}))$ is a
bottom-fence. $\gamma_{x}$ and $\gamma_{y}$ both emerge from
$\ell_{u^{\prime}}$ and thus protect $P^{\prime}$ from the left in $C_{u}$.
Hence, $P^{\prime}$ is protected by fences in $C_{u}$.

The argument is symmetric if $P^{\prime}$ is protected via (A3): there is a
polygon $Q\in\operatorname{OPT}(C_{u^{\prime}})$ seen by $P^{\prime}$ that is
intersected by the the cutting line $\ell_{u^{\prime}}$. Therefore, the curves
on $\operatorname{top}(P^{\prime})$ and $\operatorname{top}(Q)$ from
$e_{d+1}(P^{\prime})$ to $\ell_{u^{\prime}}$ and of
$\operatorname{bot}(P^{\prime})$ and $\operatorname{bot}(Q)$ from
$e_{d+1}(P^{\prime})$ to $\ell_{u^{\prime}}$ form a pair of fences that
protect $P^{\prime}$ from the right in $C_{u}$.

If $P^{\prime}$ is protected via (A1), then it has been protected for the
first time in an ancestor of $u$, so the claim follows inductively from by
(P3) and (P4).

With (P3) and (P4), Lemma 5.5 implies that protected polygons are not lost and
stay protected, i.e.,
$\operatorname{Pr}(C_{u})\subseteq\operatorname{Pr}(C_{u_{1}})\cup\operatorname{Pr}(C_{u_{2}})$
for every interior node $u$ in $T$. This in particular holds for every charged
polygon. By the construction above, every charged polygon is protected and
charged only once by Lemma 4.3. To make our charging scheme work, we need to
make sure that _every_ lost accountable polygon provides one charge, which
follows by (P2) and the following lemma.

######  Lemma 5.7.

Let $P\in\operatorname{ACC}$ be a polygon that is intersected by the vertical
line segment $\ell_{u}$ for an internal node $u\in T$. Then there exists a
polygon $P^{\prime}\in\operatorname{OPT}(C_{u})$ that is seen by $P$.

######  Proof 5.8.

Let $\mathcal{P}$ be the set of polygons seen by $P$. For the sake of
contradiction, suppose that
$\mathcal{P}\cap\operatorname{OPT}(C_{u})=\emptyset$. If some
$P^{\prime}\in\mathcal{P}$ partially lies in $C_{u}$, i.e.,
$P^{\prime}\cap\operatorname{int}(C_{u})\neq\emptyset$, then $P^{\prime}$ was
intersected by the vertical line $\ell_{u^{\prime}}$ in an ancestor
$u^{\prime}$ of $u$, so $P$ is protected via (A3). Otherwise, if all polygons
in $\mathcal{P}$ lie outside of $C_{u}$, then $e_{1}(P)$ lies on a cutting
line in $\partial C_{u}$. Therefore, $\operatorname{top}(P)$ and
$\operatorname{bot}(P)$ form a top-fence and a bottom-fence, respectively,
that protect $P$ by fences in $C_{u}$.

Figure 7: Illustration for the proof of Lemma 5.5: $P^{\prime}$ is protected
by fences via (A2).

######  Proof 5.9 (Proof of Proposition 3.5).

By Lemma 4.5, we have
$|\operatorname{ACC}|-|Z|\geq\frac{3}{4d}|\operatorname{OPT}|-|Z|$. Recall
that we have already assigned each polygon of $Z$ to a unique leaf of $T$. By
the charging scheme described above and since a protected (and thus charged)
polygon is never lost, we have a unique polygon contained in a leaf of $T$ for
each lost accountable polygon during the partition. The proposition follows
since at least half of the polygons in $\operatorname{ACC}$ are either lost,
or at least half of the polygons in $\operatorname{ACC}$ are not lost.

## References

  * [1] Anna Adamaszek, Sariel Har-Peled, and Andreas Wiese.  Approximation schemes for independent set and sparse subsets of polygons.  J. ACM, 66(4):29:1–29:40, 2019.
  * [2] Anna Adamaszek and Andreas Wiese.  A quasi-ptas for the two-dimensional geometric knapsack problem.  In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1491–1505. SIAM, 2015.
  * [3] Aris Anagnostopoulos, Fabrizio Grandoni, Stefano Leonardi, and Andreas Wiese.  A mazing 2+$\varepsilon$ approximation for unsplittable flow on a path.  In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 26–41. SIAM, 2014.
  * [4] Nikhil Bansal, Amit Chakrabarti, Amir Epstein, and Baruch Schieber.  A quasi-ptas for unsplittable flow on line graphs.  In Jon M. Kleinberg, editor, Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006, pages 721–729. ACM, 2006.
  * [5] Nikhil Bansal, Zachary Friggstad, Rohit Khandekar, and Mohammad R. Salavatipour.  A logarithmic approximation for unsplittable flow on line graphs.  ACM Trans. Algorithms, 10(1):1:1–1:15, 2014.
  * [6] Paul S. Bonsma, Jens Schulz, and Andreas Wiese.  A constant-factor approximation algorithm for unsplittable flow on paths.  SIAM J. Comput., 43(2):767–799, 2014.
  * [7] Parinya Chalermsook and Julia Chuzhoy.  Maximum independent set of rectangles.  In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 892–901. SIAM, 2009.
  * [8] Parinya Chalermsook and Bartosz Walczak.  Coloring and maximum weight independent set of rectangles.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 860–868. SIAM, 2021.
  * [9] Timothy M Chan.  Polynomial-time approximation schemes for packing and piercing fat objects.  Journal of Algorithms, 46(2):178–189, 2003.
  * [10] Timothy M. Chan and Sariel Har-Peled.  Approximation algorithms for maximum independent set of pseudo-disks.  Discret. Comput. Geom., 48(2):373–392, 2012.
  * [11] Hsien-Chih Chang, Jeff Erickson, and Chao Xu.  Detecting weakly simple polygons.  In Proceedings of the twenty-sixth annual ACM-SIAM Symposium on Discrete Algorithms, pages 1655–1670. SIAM, 2014.
  * [12] Jana Cslovjecsek, Michał Pilipczuk, and Karol Węgrzycki.  A polynomial-time $opt^{\varepsilon}$-approximation algorithm for maximum independent set of connected subgraphs in a planar graph.  In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 625–638. SIAM, 2024.
  * [13] Leila De Floriani, Paola Magillo, and Enrico Puppo.  Applications of computational geometry to geographic information systems.  Handbook of computational geometry, 7:333–388, 2000.
  * [14] Erik D Demaine and Joseph O’Rourke.  Geometric folding algorithms: linkages, origami, polyhedra.  Cambridge university press, 2007.
  * [15] Thomas Erlebach, Klaus Jansen, and Eike Seidel.  Polynomial-time approximation schemes for geometric intersection graphs.  SIAM J. Comput., 34(6):1302–1323, 2005.
  * [16] Robert J Fowler, Michael S Paterson, and Steven L Tanimoto.  Optimal packing and covering in the plane are np-complete.  Information processing letters, 12(3):133–137, 1981.
  * [17] Jacob Fox and János Pach.  Computing the independence number of intersection graphs.  In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1161–1165. SIAM, 2011.
  * [18] Takeshi Fukuda, Yasuhiko Morimoto, Shinichi Morishita, and Takeshi Tokuyama.  Data mining with optimized two-dimensional association rules.  ACM Transactions on Database Systems (TODS), 26(2):179–213, 2001\.
  * [19] Waldo Gálvez, Fabrizio Grandoni, Salvatore Ingala, Sandy Heydrich, Arindam Khan, and Andreas Wiese.  Approximating geometric knapsack via l-packings.  ACM Trans. Algorithms, 17(4):33:1–33:67, 2021.
  * [20] Waldo Gálvez, Fabrizio Grandoni, Arindam Khan, Diego Ramírez-Romero, and Andreas Wiese.  Improved approximation algorithms for 2-dimensional knapsack: Packing into multiple l-shapes, spirals, and more.  In 37th International Symposium on Computational Geometry (SoCG), volume 189, pages 39:1–39:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [21] Waldo Gálvez, Arindam Khan, Mathieu Mari, Tobias Mömke, Madhusudhan Reddy Pittu, and Andreas Wiese.  A 3-approximation algorithm for maximum independent set of rectangles.  In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 894–905. SIAM, 2022.
  * [22] 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.  arXiv preprint arXiv:2106.00623, 2021.
  * [23] Fabrizio Grandoni, Stefan Kratsch, and Andreas Wiese.  Parameterized approximation schemes for independent set of rectangles and geometric knapsack.  In Michael A. Bender, Ola Svensson, and Grzegorz Herman, editors, 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany, volume 144 of LIPIcs, pages 53:1–53:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [24] Fabrizio Grandoni, Tobias Mömke, and Andreas Wiese.  A PTAS for unsplittable flow on a path.  In Stefano Leonardi and Anupam Gupta, editors, STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 \- 24, 2022, pages 289–302. ACM, 2022.
  * [25] Fabrizio Grandoni, Tobias Mömke, and Andreas Wiese.  Unsplittable flow on a path: The game!  In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 906–926. SIAM, 2022.
  * [26] Fabrizio Grandoni, Tobias Mömke, Andreas Wiese, and Hang Zhou.  A (5/3 + $\epsilon$)-approximation for unsplittable flow on a path: placing small tasks into boxes.  In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 607–619. ACM, 2018.
  * [27] Dorit S Hochbaum and Wolfgang Maass.  Approximation schemes for covering and packing problems in image processing and vlsi.  Journal of the ACM (JACM), 32(1):130–136, 1985.
  * [28] Hiroshi Imai and Takao Asano.  Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane.  Journal of algorithms, 4(4):310–323, 1983.
  * [29] Klaus Jansen and Guochuan Zhang.  On rectangle packing: maximizing benefits.  In J. Ian Munro, editor, Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 204–213. SIAM, 2004.
  * [30] Sanjeev Khanna, S. Muthukrishnan, and Mike Paterson.  On approximating rectangle tiling and packing.  In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 384–393. ACM/SIAM, 1998.
  * [31] James T Klosowski, Martin Held, Joseph SB Mitchell, Henry Sowizral, and Karel Zikan.  Efficient collision detection using bounding volume hierarchies of k-dops.  IEEE transactions on Visualization and Computer Graphics, 4(1):21–36, 1998.
  * [32] Yoshiyuki Kusakari, Hitoshi Suzuki, and Takao Nishizeki.  A shortest pair of paths on the plane with obstacles and crossing areas.  International Journal of Computational Geometry & Applications, 9(02):151–170, 1999.
  * [33] Brian Lent, Arun Swami, and Jennifer Widom.  Clustering association rules.  In Proceedings 13th International Conference on Data Engineering, pages 220–231. IEEE, 1997.
  * [34] Ewa Malesinska.  Graph theoretical models for frequency assignment problems.  Citeseer, 1997.
  * [35] Dániel Marx.  Efficient approximation schemes for geometric problems?  In 13th Annual European Symposium on Algorithms (ESA), volume 3669, pages 448–459. Springer, 2005.
  * [36] Joseph S. B. Mitchell.  Approximating maximum independent set for rectangles in the plane.  CoRR, abs/2101.00326, 2021.  Version 1.
  * [37] Joseph SB Mitchell.  Approximating maximum independent set for rectangles in the plane.  In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 339–350. IEEE, 2022.
  * [38] Frank Nielsen.  Fast stabbing of boxes in high dimensions.  Theor. Comput. Sci., 246(1-2):53–72, 2000.
  * [39] Bram Verweij and Karen Aardal.  An optimisation algorithm for maximum independent set with applications in map labelling.  In Algorithms-ESA’99: 7th Annual European Symposium Prague, Czech Republic, July 16–18, 1999 Proceedings 7, pages 426–437. Springer, 1999\.
  * [40] Andreas Wiese.  Independent set of convex polygons: From $n^{\epsilon}$ to $1+\epsilon$ via shrinking.  Algorithmica, 80(3):918–934, 2018.

##  Appendix A Maximal extension

For convenience, we restate the definition of a maximal extension. See 4.1

Recall that $\mathcal{L}_{1}$ is the set of all lines in directions
$v_{1},\dots,v_{d}$ passing through the corners of input polygons, and that
$\mathcal{V}_{k}$, for $k\in[2d]$ and $\mathcal{L}_{k}$, for
$k\in\\{2,\dots,2d\\}$ are recursively defined as follows: $\mathcal{V}_{k}$
is the set of intersection points of any two (non-parallel) lines in
$\mathcal{L}_{k}$, and $\mathcal{L}_{k}$ is the set of all lines in directions
$\mathcal{D}$ spanned from all points in $\mathcal{V}_{k-1}$. In particular,
$C^{*}\in\mathcal{G}_{1}$ and $P\in\mathcal{G}_{1}$ for every
$P\in\operatorname{OPT}$.

######  Lemma A.1.

There exists a maximal extension of $\operatorname{OPT}$.

######  Proof A.2.

We describe a process by which, sequentially, every edge of every polygon in
$\operatorname{OPT}$ is extended at most once, such that the resulting
instance is a maximal extension of the input instance (so we have (E2) by
construction). We use the following claim which is simple to prove.

######  Claim 2.

Two polygons $P,P^{\prime}\in\mathcal{I}$ intersect if and only if
$p_{i}(P)>-p_{i+d}(P^{\prime})$ for every $i\in[2d]$.

First, for every $P\in\operatorname{OPT}$, we initialize $D(P)$ as the set of
all indices $i\in[2d]$ such that $e_{i}(P)$ is degenerate. We want to assure
that for every $i\in D(P)$, $e_{i}(P)$ stays degenerate during the extension,
unless it separates $P$ from another polygon, so we set $p_{i}(P)=+\infty$ for
every $i\in D(P)$.

We repeat the following sweep line algorithm for every $i\in[2d]$: for every
polygon $P\in\operatorname{OPT}$ at a time, unless $i\in D(P)$, continuously
increase $p_{i}(P)$ (we say that we _extend $P$ in the $i$-th direction_)
until one of the following _events_ occurs, see Figure 8.

  1. [S1]

$P$ touches some $\tilde{P}\in\operatorname{OPT}$ (or $\partial C^{*}$) but
$\operatorname{int}(e_{i}(P))$ does not overlap with $\partial\tilde{P}$ (or
$\partial C^{*}$) and $P$ intersects $\tilde{P}$ (or the exterior of $C^{*}$)
if $p_{i}(P)$ is increased any further.

  2. [S2]

$\operatorname{int}(e_{i}(P))$ overlaps with $\partial\hat{P}$ for some
$\hat{P}\in\operatorname{OPT}$ or $\partial C^{*}$.

  3. [S3]

$e_{i}(P)$ becomes degenerate.

To shorten the analysis, we assume without loss of generality that at [S1] and
[S2], we always touch some polygon $\tilde{P}$ or $\hat{P}$, respectively,
instead of $\partial C^{*}$. Whenever we encounter [S1] (assuming it does not
happen at the same time as [S2] or [S3]), then it means that $P$ touches a
(non-degenerate) edge $e_{j+d}(\tilde{P})$ such that $j\notin\\{i,i+d\\}$ (and
such that $\operatorname{int}(e_{j+d}(\tilde{P}))$ intersects $P$ if we extend
it further). Set $p_{j}(P)=-p_{j+d}(\tilde{P})$, remove $j$ from $D(P)$ and
then keep on increasing $p_{i}(P)$. When [S2] occurs, stop increasing
$p_{i}(P)$. In case [S3] occurs, stop increasing $p_{i}(P)$, add $i$ to $D(P)$
and set $p_{i}(P)=+\infty$.

(a)

(b)

Figure 8:  The polygon $P$ is extended in the $i$-th direction. The position
of $e_{i}(P)$ at each event is highlighted. The point and line highlighted in
red lie on $\mathcal{G}_{i}$, all other points and lines lie on
$\mathcal{G}_{i-1}$.

It is clear that the extension of $e_{i}(P)$ must finish by either [S2] or
[S3], since otherwise $P$ grows indefinitely which contradicts
$P\subseteq\operatorname{int}(C^{*})$. On the other hand, $P$ can be extended
as long as [S2] or [S3] has not occurred. Whenever [S1] occurs, then at the
moment of contact, the edges $e_{j+d}(\tilde{P})$ and $e_{j}(P)$ overlap, see
Figure 8(a). However since increasing $P$ further in the $i$-th direction
makes $P$ and $\tilde{P}$ intersect, so we have $p_{j}(P)>-p_{j+d}(\tilde{P})$
by Claim 2. This means that the $j$-th constraint of $P$ is redundant and in
particular that $e_{j}(P)$ is degenerate until the moment of contact between
$P$ and $\tilde{P}$. By setting $p_{j}(P)=-p_{j+d}(\tilde{P})$, we can
continue to extend $P$ in the $i$-th direction without causing an intersection
between $P$ and $\tilde{P}$. Notice that starting from now, increasing
$p_{j}(P)$ causes an intersection between $P$ and $\tilde{P}$. In particular,
it is a non-redundant constraint. Therefore, $e_{j}(P)$ will never be
degenerate again once $p_{i}(P)$ is increased further.

We now argue that (E1) and (E3) hold by proving the two following claims.

######  Claim 3.

After the extension process, $\operatorname{OPT}$ lies on $\mathcal{G}_{2d}$.

We proceed by induction in the number of extensions, i.e., show that
$\operatorname{OPT}$ lies on $\mathcal{G}_{k}$ once it has been extended in
$k$ directions.

Assume now that $\operatorname{OPT}$ has been extended in $i-1$ directions,
where $i\in\\{1,\dots,2d\\}$. We focus on the extension in the $i$-th
direction of a single $P\in\operatorname{OPT}$. Assume first that no polygon
has been extended in the $i$-th direction yet, meaning that
$P^{\prime}\in\mathcal{G}_{i-1}$ for every $P^{\prime}\in\operatorname{OPT}$
by assumption. We show that at any event [S1], [S2] or [S3],
$P\in\mathcal{G}_{i}$ is maintained. Assume $i\notin D(P)$ and let $i_{1}$ and
$i_{2}$ be the indices of the two non-degenerate edges incident to $e_{i}(P)$
(w.l.o.g. $h(e_{i_{1}}(P))=t(e_{i}(P))$, $t(e_{i_{2}}(P))=h(e_{i}(P))$ and
$i_{1}<i<i_{2}$). Notice during the continuous extension of $P$ in the $i$-th
direction, $e_{i_{1}}$ and $e_{i_{2}}$ get prolonged and all the edges
$e_{i^{\prime}}(P)$, for $i^{\prime}\notin\\{i,i_{1},i_{2}\\}\cup D(P)$, are
not altered.

At [S1], assume that $e_{j+d}(\tilde{P})$ touches $t(e_{i}(P))$ (the argument
is identical if it touches $h(e_{i}(P))$) and therefore $e_{j}(P)$ as well.
This means that $i_{1}<j<i$. In particular, once we have set
$p_{j}(P)=-p_{j+d}(\tilde{P})$ and continue extending $P$, $e_{j}(P)$ is now a
non-degenerate edge incident to $e_{i}(P)$ while $e_{i_{1}}$ does not change
any longer. We have $e_{i_{1}}\in\mathcal{L}_{i-1}$ since it has only be
prolonged since the beginning of the extension, and
$e_{j}(P)\in\mathcal{L}_{i-1}$ since it is collinear with
$e_{j+d}(\tilde{P})$. Notice that
$t(e_{j}(P))=h(e_{i_{1}}(P))\in\mathcal{V}_{i-1}$. Now substitute $i_{1}=j$
and repeat the argument for the upcoming events.

When we arrive at [S2], all edges of $P$ lie on $\mathcal{L}_{i-1}$, since
$e_{i}(P)$ is collinear with $e_{i+d}(\hat{P})\in\mathcal{L}_{i-1}$. Every
vertex of $P$ lies on $\mathcal{V}_{i-1}$.

At [S3], we have $e_{i^{\prime}}(P)\in\mathcal{L}_{i-1}$ for every
$i^{\prime}\neq i$, and every vertex of $P$ lies on $\mathcal{V}_{i-1}$. This
implies $e_{i}(P)\in\mathcal{L}_{i}$.

Assume now $P$ that is not the first polygon to get extended in the $i$-th
direction. If [S1] occurs and $\tilde{P}$ has already been extended in the
$i$-th direction, since $j\notin\\{i,i+d\\}$, we have
$e_{j+d}(\tilde{P})\in\mathcal{L}_{i-1}$ and thus
$e_{j}(P)\in\mathcal{L}_{i-1}$ as well. Similarly, at [S2], we have
$e_{i+d}(\hat{P})\in\mathcal{L}_{i-1}$ (for any
$P^{\prime}\in\operatorname{OPT}$, $e_{i+d}(P^{\prime})$ stays intact since it
is parallel to $e_{i}(P^{\prime})$, i.e., $i_{1}\neq i+d$, $i_{2}\neq i+d$),
so $e_{i}(P)\in\mathcal{L}_{i-1}$ and every vertex of $P$ lies on
$\mathcal{V}_{i}$. For [S3], there is nothing more to show since is does not
establish contact of $P$ with a new polygon.

######  Claim 4.

After the extension process, $\operatorname{OPT}$ satisfies (E3).

Clearly, for any $P\in\operatorname{OPT}$, $i\in[2d]$, immediately after the
extension of $P$ in the $i$-th direction (assuming $i\notin D(P)$ before the
extension), $e_{i}(P)$ satisfies (E3). If the extension of $P$ in the $i$-th
direction has ended with [S2], then increasing $p_{i}(P)$ makes $P$ and
$\hat{P}$ intersect. This means that $e_{i}(P)$ is not degenerate, and
$\operatorname{int}(e_{i}(P))$ is non-empty. In particular,
$\operatorname{int}(e_{i}(P))$ touches $\hat{P}$ and satisfies (E3) at the end
of the process. If the extension of $P$ in the $i$-th direction has ended with
[S3], then either $e_{i}(P)$ stays degenerate until the end (so (E3) is
trivially satisfied) or it becomes non-degenerate during the extension of $P$
in another direction than $i$. The latter case occurs at the event [S1] during
the extension of $P$ in some direction
$i^{\prime}\in[2d]\setminus\\{i,i+d\\}$, when $e_{i^{\prime}}(P)$ touches some
$\tilde{P}\in\operatorname{OPT}$ on the edge $e_{i+d}(\tilde{P})$. Then, the
algorithm sets $p_{i}(P)=-p_{i+d}(\tilde{P})$ and continues the extension of
$P$ in the $i^{\prime}$-th direction, which prolongates $e_{i}(P)$. As argued
above, at the end of the entire extension process, $e_{i}(P)$ is non-
degenerate, and $\operatorname{int}(e_{i}(P))$ touches $\tilde{P}$, thus
satisfying (E3).

##  Appendix B Proof of the partitioning lemma

See 5.4

######  Proof B.1.

Let $C$ be a structured container with boundary $\partial
C=s_{1}f_{1}s_{2}f_{2}\cdots s_{\kappa}f_{\kappa}$, where
$s_{1},\dots,s_{\kappa}$ are cutting lines and $f_{1},\dots,f_{\kappa}$ are
fences (to facilitate the proof, we write $s_{\kappa+1}=s_{1}$ and
$f_{\kappa+1}=f_{1}$). Moreover, for some index $\kappa^{\prime}$ with
$\kappa^{\prime}<\kappa$, the cutting lines $s_{1},\dots,s_{\kappa^{\prime}}$
are left cutting lines and $s_{\kappa^{\prime}+1},\dots,s_{5}$ are right
cutting lines. We also assume that $\kappa$ is minimal, i.e., $f_{j}\cup
s_{j+1}\cup f_{j+1}$ never forms a fence (otherwise we merge these curves onto
one fence $\tilde{f}$ and $s_{1}f_{1}\cdots,s_{j}\tilde{f}s_{j+2}\cdots
f_{\kappa}$ is still the boundary of $C$ but the index $\kappa$ decreases).
Without loss of generality, we assume that
$\kappa^{\prime}\geq\lceil\frac{\kappa}{2}\rceil$, that is, we assume that
there are not less left cutting lines than right cutting lines, otherwise we
mirror the instance vertically. We first treat the case when $\kappa=5$. In
particular, we have $\kappa^{\prime}\geq 3$. We will address the proof of
cases with $\kappa\leq 4$ at the end of the proof since it suffices to adapt
the arguments made for $\kappa=5$.

Without loss of generality, we assume that $C$ contains no spurs. A _spur_ is
a vertex whose two incident edges overlap, this might happen if some line
segment $s_{j}$ is degenerate and the two edges in $f_{j}$ and $f_{j+1}$ that
are incident to $s_{j}$ overlap. If the edges $\overline{w^{\prime}w}$ and
$\overline{ww^{\prime\prime}}$ form a spur around $w$, then replace those two
edges with the new edge $\overline{w^{\prime}w^{\prime\prime}}$ and reiterate
this procedure as long as there is a spur. Removing spurs this way does not
decrease the interior of a container nor create any new crossing. In
particular, any polygon (with non-crossing, positively oriented boundary) has
non-empty interior if and only if its boundary is non-degenerate once all
spurs are removed.

Suppose there exists a polygon $P_{0}$ in $C$ protected from the left via
$s_{2}$; take such $P_{0}$ with the right-most right edge (breaking ties
arbitrarily). Since $P_{0}$ is protected (see Definition 5.3) from the left
via $s_{2}$, there exist a top-fence $\gamma_{h}$ emerging from $s_{2}$ with
endpoint $h=h(e_{1}(P_{0}))$ and a bottom-fence $\gamma_{t}$ emerging from
$s_{2}$ with endpoint $t=t(e_{1}(P_{0}))$.

Now, let $p_{h}$ and $p_{t}$ be the two points that satisfy the following
conditions:

  1. (i)

$p_{h}$ and $p_{t}$ are in the same vertical line as $h$ and $t$ such that
$p_{h}$ is above or coincides with $h$ and $p_{t}$ is below or coincides with
$t$.

  2. (ii)

$p_{h}$ (resp. $p_{t}$) lies either on $\partial C$ or on $\partial
P_{h}\setminus(e_{1}(P_{h})\cup e_{d+1}(P_{h}))$ (resp. $\partial
P_{t}\setminus(e_{1}(P_{t})\cup e_{d+1}(P_{t}))$), where
$P_{h}\in\operatorname{OPT}(C)$ (resp. $P_{t}\in\operatorname{OPT}(C)$) is
protected in $C$.

  3. (iii)

The semi-open vertical line segments $\overline{hp_{h}}\setminus\\{h\\}$ and
$\overline{tp_{t}}\setminus\\{t\\}$ do not contain any point that satisfies
condition (ii).

It is clear that these two points exist and are unique. We will construct
$\Gamma$ by case analysis, depending on the location of $p_{h}$ and $p_{t}$.

Figure 9: Illustration of the notation used to construct $C_{1}$ and $C_{2}$
according to the location of $p_{h}$ and $p_{t}$. In this example, $C_{1}$ has
boundary $\partial C_{1}=\Gamma f_{5}^{+}s_{1}f_{1}s_{2}^{-}$ and $C_{2}$ has
boundary $\partial
C_{2}=s_{2}^{+}f_{2}s_{3}f_{3}s_{4}f_{4}s_{5}f_{5}^{-}\Gamma^{-}$.

Before we proceed, let us first introduce some notation that allows us to
define the boundaries of $C_{1}$ and $C_{2}$ in a compact form, see Figure 9.
For $i\in[\kappa]$, $r_{i}\in\\{s_{i},f_{i}\\}$ and
$c\in\\{h(\Gamma),t(\Gamma)\\}$ (as it will be defined below) such that $c\in
r_{i}$, we define $r_{i}^{+}$ to be the curve on $r_{i}$ from $c$ to
$h(r_{i})$ and $r_{i}^{-}$ to be the curve on $r_{i}$ from $t(r_{i})$ to $c$
($r_{i}^{+}$ or $r_{i}^{-}$ might only consist of a singleton point). In
particular, $r_{i}=r_{i}^{-}r_{i}^{+}$ and $t(r_{i}^{-})=t(r_{i})$,
$h(r_{i}^{-})=c=t(r_{i}^{+})$ and $h(r_{i}^{+})=h(r_{i})$. For the oriented
curve $\Gamma$ that we will define below, let $\Gamma^{-}$ be $\Gamma$ but
with inverse orientation (i.e., $h(\Gamma^{-})=t(\Gamma)$ and
$t(\Gamma^{-})=h(\Gamma)$).

We first cover the simplest cases, namely when $P_{0}$ exists and
$\operatorname{int}(e_{1}(P_{0}))\subseteq\operatorname{int}(C)$, which are
illustrated in Figure 10.

  1. (A1)

Both $p_{h}$ and $p_{t}$ lie on $f_{1}\cup f_{2}$. This implies $p_{h}\in
f_{1}$ and $p_{t}\in f_{2}$ since $f_{1}$ lies above $f_{2}$.555For two
objects $A,B\subseteq\mathbb{R}^{2}$, we say that _$A$ lies above (below) $B$_
if for every $(a,b)\in A\times B$ such that $a$ and $b$ have the same
$x$-coordinate, $a$ has larger (smaller) $y$-value than $b$. We define _lying
on the left_ or _right_ analogously. Choose $\Gamma=\overline{p_{h}p_{t}}$,
thus $\partial C_{1}=\Gamma f_{2}^{+}s_{3}\cdots s_{1}f_{1}^{-}$ and $\partial
C_{2}=f_{1}^{+}s_{2}f_{2}^{-}\Gamma^{-}$.

  2. (A2)

$p_{h}$ or $p_{t}$ (or both) lies on $\bigcup_{i\geq 3}f_{i}$. Assume that
$p_{t}\in f_{j}$, $j\geq 3$ (if $p_{t}$ lies on multiple fences, choose $j$ to
be the smallest index). Choose $\Gamma=\gamma_{h}\overline{hp_{t}}$, thus
$\partial C_{1}=\Gamma f_{j}^{+}s_{j+1}\cdots,f_{1}s_{2}^{-}$ and $\partial
C_{2}=s_{2}^{+}f_{2}\cdots f_{j}^{-}\Gamma^{-}$.

  3. (A3)

$P_{h}$ or $P_{t}$ (or both) exists and is protected from the right in $C$.
Assume that $P_{h}$ is protected from the right. Let $\delta_{h}$ be a bottom-
fence starting at $p_{h}$ and ending on some right cutting line $s_{j}$ that
protects $P_{h}$. Choose $\Gamma=\gamma_{h}\overline{hp_{h}}\delta_{h}$, thus
$\partial C_{1}=\Gamma s_{j}^{+}f_{j}\cdots f_{1}s_{2}^{-}$ and $\partial
C_{2}=s_{2}^{+}f_{2}\cdots,f_{j-1}s_{j}^{-}\Gamma^{-}$.

  4. (A4)

Both $P_{h}$ and $P_{t}$ exist and are protected from the left in $C$. From
condition (ii), there exists a bottom-fence $\delta_{h}$ from $s_{1}$ to
$p_{h}$ which protects $P_{h}$ and terminating in $p_{h}$ and a top-fence
$\delta_{t}$ from $s_{j}$ ($3\leq j\leq\kappa^{\prime}$) to $p_{t}$ which
protects $P_{t}$. Choose $\Gamma=\delta_{h}\overline{p_{h}p_{t}}\delta_{t}$,
thus $\partial C_{1}=\Gamma s_{j}^{+}f_{j}\cdots f_{5}s_{1}^{-}$ and $\partial
C_{2}=s_{1}^{+}f_{1}s_{2}\cdots s_{j}^{-}\Gamma^{-}$.

  5. (A5)

$P_{t}$ exists and is protected from the left in $C$ and $p_{h}\in f_{1}$; or
$P_{h}$ exists and is protected from the left in $C$ and $p_{t}\in f_{2}$.
Without loss of generality, assume the first situation. Let $\delta_{t}$ be
the top-fence from $s_{j}$ ($3\leq j\leq\kappa^{\prime}$) to $p_{t}$ which
protects $P_{t}$. Choose $\Gamma=\overline{p_{h}p_{t}}\delta_{t}$, thus
$\partial C_{1}=\Gamma s_{j}^{+}f_{j}\cdots s_{1}f_{1}^{-}$ and $\partial
C_{2}=f_{1}^{+}s_{2}\cdots f_{j-1}s_{j}^{-}\Gamma^{-}$.

(a)

(b)

(c)

(d)

(e)

Figure 10:  Bipartitions of $C$ for
$\operatorname{int}(e_{1}(P_{0}))\subseteq\operatorname{int}(C)$. The areas
$\operatorname{int}(C_{1})$ (orange) and $\operatorname{int}(C_{2})$ (yellow),
are separated by the highlighted curve $\Gamma$ ($\gamma_{h},\gamma_{t}$ in
blue, $\ell$ in green, $\delta_{h},\delta_{t}$ in orange).

Now, we discuss the instances where $P_{0}$ exists but
$\operatorname{int}(e_{1}(P_{0}))\not\subseteq\operatorname{int}(C)$, or
equivalently, $\operatorname{int}(e_{1}(P_{0}))\cap\partial C\neq\emptyset$,
see Figure 11. For (B1), $\Gamma$ can be constructed straight away, while (B2)
reduces to one of (A1) to (A5) by redefining $p_{h}$ and $p_{t}$ as an
intermediate step.

  1. (B1)

$\overline{p_{h}p_{t}}$ overlaps a right cutting line $s_{j}$. Assume
$p_{h}\in s_{j}$. Choose $\Gamma=\gamma_{h}$, thus $\partial C_{1}=\Gamma
s_{j}^{+}f_{j}\cdots s_{1}f_{1}s_{2}^{-}$ and $\partial
C_{2}=s_{2}^{+}f_{2}\cdots s_{j}^{-}\Gamma^{-}$.

  2. (B2)

$\operatorname{int}(e_{1}(P_{0}))$ intersects a fence $f_{j}$. Assume that
$f_{j}$ is oriented from left to right. Therefore $t\in f_{j}$, and
$e_{1}(P_{0})$ intersects the interior of the vertical line $\tilde{e}$ of a
top-fence on $\partial C$, thus $\tilde{e}=e_{d+1}(\tilde{P})$ for some
$\tilde{P}\in\operatorname{OPT}\setminus\operatorname{OPT}(C)$; furthermore
$j\notin\\{1,5\\}$. We redefine $p_{h}$ and $p_{h}$: if $j\neq 2$, then set
$p_{t}$ and $p_{h}$ as $t(\tilde{e})$ or $h$, whichever lies lower. and then
construct $\Gamma$ as in (A2), i.e., $\Gamma=\gamma_{h}\overline{hp_{t}}$ and
$\partial C_{1}$, $\partial C_{2}$ accordingly. For $j=2$, set
$p_{t}=t(\tilde{e})$, and then recompute $p_{h}$ according to (i), (ii) and
(iii) and additionally such that any point in the semi-open vertical line
segment $\overline{t(\tilde{e})p_{h}}\setminus\\{t(\tilde{e})\\}$ satisfies
(ii) (so $p_{h}$ lies above $f_{2}$). Then, we apply the case analysis and
construction of the cases (A1) to (A5). Notice that in any case, we have
$\operatorname{int}(\overline{p_{h}p_{t}})\subseteq\operatorname{int}(C)$.

(a)

(b)

Figure 11:  Bipartitions of $C$ if the right side of $P_{0}$ touches $\partial
C$. $\operatorname{int}(C_{1})$ is orange, $\operatorname{int}(C_{2})$ is
yellow.

We now consider instances where $P_{0}$ does not exist, see Figure 12. If
$s_{1}$ and $s_{3}$ both lie on the right of $s_{2}$, then it suffices to
“shift” $s_{2}$ a little to the right, as defined in (C1). Otherwise, i.e., in
(C3), we make $\ell$ going down (or up) starting from the bottom (resp. top)
of $s_{2}$ and reduce it to simpler cases, depending on the location of
$p_{h}$ and $p_{t}$. There might also occur another very particular case,
namely if there is one or two polygons that touches $s_{2}$ on its top and/or
bottom (so $\ell$ is degenerate) and is protected from the left by $f_{2}$
resp. $f_{1}$, so there is no “gap” above resp. below the polygon(s). We have
to handle this case individually.

Let us describe the latter case more formally. Assume that $s_{3}$ lies on the
left of $s_{2}$, and let $P_{3}$ be the polygon in $\operatorname{OPT}(C)$ (if
it exists) with  1. $h(s_{2})$lies on the bottom (but not on the side) of
$P_{3}$ 2. $P_{3}$is protected from the left via $s_{3}$ 3. for the top-fence
$\mu_{3}$ protecting $P_{3}$, we have $f_{2}\subseteq\mu_{3}$.  If $s_{1}$
lies on the left of $s_{2}$, the polygon $P_{1}\in\operatorname{OPT}(C)$, if
it exists, touches $t(s_{2})$ on its bottom (and the bottom-fence
$\mu_{1}\supseteq f_{1}$ protecting $P_{1}$), is defined symmetrically.

  1. (C1)

$P_{0}$ does not exist and $s_{1}$ and $s_{2}$ both lie on the right of
$s_{2}$. Choose $\Gamma$ to be any vertical line segment $\ell$ (on
$\mathcal{G}_{2d}$) with $t(\ell)\in f_{1}$ and $h(\ell)\in f_{2}$ which lies
strictly on the right of $s_{2}$ and that does not intersect any polygon in
$\operatorname{OPT}(C)$. If $\ell$ does not exist, then the leftmost
$P\in\operatorname{OPT}$ between $f_{1}$ and $f_{2}$ must touch $s_{2}$ and is
therefore protected, which contradicts the nonexistence of $P_{0}$. Then
$C_{1}$ and $C_{2}$ are constructed as in (A1), i.e., $\partial C_{1}=\Gamma
f_{2}^{+}s_{3}\cdots s_{1}f_{1}^{-}$ and $\partial
C_{2}=f_{1}^{+}s_{2}f_{2}^{-}\Gamma^{-}$.

  2. (C2)

$P_{0}$ does not exist and either: $s_{1}$ lies on the right of $s_{2}$ and
$P_{3}$ exists, or $s_{3}$ lies on the right of $s_{2}$ and $P_{1}$ exists, or
both $P_{1}$ and $P_{3}$ exist. Let us first consider the former occurrence,
i.e., when $s_{1}$ lies on the right of $s_{2}$ and $P_{3}$ exists (the
construction for the second one is analogous). We assume that $s_{2}$ is non-
degenerate or that the segment of $\mu_{3}$ on the right of $s_{2}$ does not
form a spur with $f_{1}$. Indeed, otherwise $s_{2}$ can be dragged at the
right extreme point of the spur. Let $\ell$ be any vertical line segment (on
$\mathcal{G}_{2d}$) strictly on the right of $s_{2}$ with $t(\ell)\in f_{1}$
and $h(\ell)\in\mu_{3}$ that does not intersect any polygon in
$\operatorname{OPT}(C)$. $\ell$ exists by the same argument as in (C1). Let
$\mu_{3}^{\prime}$ be the segment of $\mu_{3}$ from $h(\ell)$ to $h(s_{2})$
and choose $\Gamma=\ell\mu_{3}^{\prime}$, thus $\partial C_{1}=\Gamma
f_{2}s_{3}\cdots s_{1}f_{1}^{-}$ and $\partial
C_{2}=f_{1}^{+}s_{2}\Gamma^{-}$.

We construct $\Gamma$ similarly when both $P_{1}$ and $P_{3}$ exist. Again, we
assume that $s_{2}$ is non-degenerate or that the segments of $\mu_{1}$ and
$\mu_{3}$ on the right of $s_{2}$ do not form a spur, since otherwise $s_{2}$
can be dragged at the right extreme point of that spur. Let $\ell$ be any
vertical line segment (on $\mathcal{G}_{2d}$) strictly on the right of $s_{2}$
with $t(\ell)\in\mu_{1}$ and $h(\ell)\in\mu_{3}$ that does not intersect any
polygon in $\operatorname{OPT}(C)$. Let $\mu_{3}^{\prime}$ defined as above
and $\mu_{1}^{\prime}$ be the segment of $\mu_{1}$ from $h(t(s_{2}))$ to
$t(\ell)$ and choose $\Gamma=\mu_{1}^{\prime}\ell\mu_{3}^{\prime}$, thus
$\partial C_{1}=\Gamma f_{2}s_{3}\cdots s_{1}f_{1}$ and $\partial
C_{2}=s_{2}\Gamma^{-}$.

  3. (C3)

$P_{0}$ does not exist and $s_{1}$ or $s_{3}$ (or both) lie on the left of
$s_{2}$, and without (C2) Assume $s_{3}$ lies on the left of $s_{2}$, i.e.,
$f_{2}$ is oriented from right to left. Define $h=t=p_{h}=h(s_{2})$,
$\gamma_{h}=\gamma_{t}=\\{h(s_{2})\\}$ and $p_{t}$ according to (i), (ii), and
such that any point on the semi-open vertical line segment
$\overline{h(s_{2})p_{t}}\setminus\\{h(s_{2})\\}$ satisfies (ii) (so $p_{t}$
lies below $h(s_{2})$). If now $p_{t}\in\bigcup_{i\geq 3}f_{i}$ or $P_{t}$ is
protected from the right, proceed as in (A2) or (A3), respectively. In the
case that $P_{t}$ is protected from the left, let $\delta_{t}$ be the top-
fence which protects $P_{t}$ (from the left cutting line $s_{j}$, $3\leq
j\leq\kappa^{\prime}$ to $p_{t}$). Then choose
$\Gamma=\overline{p_{h}p_{t}}\delta_{t}$ and therefore $\partial C_{1}=\Gamma
s_{j}^{+}f_{j}\cdots f_{1}s_{1}$ and $\partial C_{2}=f_{2}s_{2}\dots
s_{j}^{-}\Gamma^{-}$ (this case is similar to (A5)).

(a)

(b)

(c)

(d)

Figure 12:  Bipartitions of $C$ if $P_{0}$ does not exist. The cutting line
$\ell$ (green) lies on the right of $\operatorname{int}(C_{1})$ and on the
left of $\operatorname{int}(C_{2})$.

For every case, it is clear that $\ell=\Gamma\cap\overline{p_{h}p_{t}}$ does
not intersect any protected polygon by the criteria (i), (ii) and (iii). For
every case, it is also easy to verify that $\Gamma\setminus\ell$ is a union of
fences. Since fences do not intersect any polygon in $\operatorname{OPT}$ by
definition, (P2) and (P3) follow from these observations. Notice also that
(P4) follows from (P1) and (P3): For any $P\in\Pr(C)$ that is protected in $C$
by fences $\sigma_{h},\sigma_{t}$ via $s$, we have
$P\in\operatorname{OPT}(C_{1})$ or $P\in\operatorname{OPT}(C_{2})$ by (P1) and
(P3). Assuming the former, then either $\ell$ crosses the fences protecting
$P$, so then the segments of $\sigma_{h},\sigma_{t}$ starting from $\ell$ form
a new pair of fences in $C_{1}$ that protect $P$ in $C_{1}$ via $\ell$, or
otherwise, $\sigma_{h},\sigma_{t}$ lie on $C_{1}$ and protect $P$ in $C_{1}$
via $s$ as before. We have $P\in\Pr(C_{1})$ in both cases. Therefore, to
finish the proof (for $\kappa=5$), we need to show (P1).

It is simple to verify that the polygons $C_{1},C_{2}$ constructed above are
structured, i.e., that their boundaries consist each of at most five disjoint
vertical cutting lines and five fences that alternate, for every case treated
above. It remains to show that $C_{1}$ and $C_{2}$ are indeed containers,
i.e., that they have non-empty interior and no crossings, and that they
partition the interior of $C$.

######  Claim 5.

Both $C_{1}$ and $C_{2}$ as constructed by Lemma 5.4 have non-empty interior.

We can argue either by proving $\operatorname{int}(C_{i})\neq\emptyset$
directly or by proving that $\partial C_{1}$ and $\partial C_{2}$ are non-
degenerate curves once all spurs are deleted. Since $\partial C$ and $\Gamma$
by themselves contain no spurs (by assumption and construction, respectively),
for every construction of $\Gamma$, it suffices to show either
$\Gamma\setminus\partial C\neq\emptyset$, or $\partial
C_{1}\setminus\Gamma\neq\emptyset$ and $\partial
C_{2}\setminus\Gamma\neq\emptyset$. It is simple to verify that
$\overline{p_{h}p_{t}}$ does not form any spur with $\partial C$, so if $\ell$
is non-degenerate, the claim holds as well. We argue case by case.

(A1).

We have
$\operatorname{int}(\Gamma)=\operatorname{int}(\ell)\subseteq\operatorname{int}(C)$,
which excludes any spur.

(A2).

Assume $p_{t}\in f_{j}$, $j\geq 3$. If $\partial
C_{1}\setminus\Gamma=\emptyset$, we have
$\Gamma^{-}=f_{j}^{+}s_{j+1}\cdots,f_{1}s_{2}^{-}$, and thus the contradiction
that $f_{5}s_{1}f_{1}$ forms a fence. We have
$\operatorname{int}(C_{i})\neq\emptyset$ since
$P_{0}\in\operatorname{int}(C_{2})$.

(A3).

Assume $P_{h}$ is protected from the right. We have $\partial
C_{2}\setminus\Gamma\neq\emptyset$ because $\gamma_{h}$ lies (strictly) above
$\gamma_{t}$, which itself lies above $f_{2}$, so $\gamma_{h}$ cannot form any
spur with $f_{2}$. Similarly, we have $\partial
C_{1}\setminus\Gamma\neq\emptyset$ because $\delta_{h}$ cannot form a spur
with $f_{j}$, since $\delta_{h}$ (which is a bottom-fence) lies (strictly)
below $f_{j}$.

(A4).

We have $P_{t}\in\operatorname{int}(C_{1})$ and
$P_{0}\in\operatorname{int}(P_{0})$.

(A5).

Same argument as for (A4).

(B1).

We have $\Gamma=\gamma_{h}\subseteq\partial C$ if and only if $s_{j}^{+}$ and
$s_{2}^{-}$ are singletons and $\Gamma^{-}=f_{j}\cdots s_{1}f_{1}$, which
contradicts the assumption that $f_{5}s_{1}f_{1}$ cannot form a fence, thus
$\Gamma\setminus\partial C\neq\emptyset$.

(B2).

The argument reduces to the cases (A1) to (A5).

(C1).

Same argument as for (A1).

(C2).

The claim follows from the assumption that $f_{1}$ and $\mu_{3}^{\prime}$ or
$\mu_{1}^{\prime}$ and $\mu_{3}^{\prime}$ do not form any spur.

(C3).

We can assume $p_{t}=p_{h}$, otherwise $\ell$ is non-degenerate. If $p_{t}\in
f_{j}$, $j\geq 3$, then $\Gamma=\\{h(s_{2})\\}$, so $\partial
C_{1}\setminus\Gamma\neq\emptyset$ and $\partial
C_{2}\setminus\Gamma\neq\emptyset$ trivially hold. Else, if $P_{t}$ exists
(i.e., $\Gamma=\delta_{t}$), then $\partial C_{1}\setminus\Gamma\neq\emptyset$
because $s_{2}\in\partial C_{1}$, and $\partial
C_{2}\setminus\Gamma\neq\emptyset$ because $f_{2}\setminus\Gamma\neq\emptyset$
(either because $P_{t}$ is protected from the right or because otherwise we
are in (C2)).

######  Claim 6.

The respective boundaries of $C_{1}$ and $C_{2}$ contain no crossings.

For every case, the claim follows from one or many of those statements:

  1. (1)

There is no crossing on $\Gamma$.

  2. (2)

There are also no crossings on $\partial C_{1}\setminus\Gamma$ and there are
also no crossings on $\partial C_{2}\setminus\Gamma$.

  3. (3)

$\partial C$ and $\ell$ do not cross.

  4. (4)

Any fence does in $C$ does not cross $\partial C$.

We now prove those statements.

For all cases but (A4) and (C2) (when both $P_{1}$ and $P_{3}$ exist),
$\Gamma$ is horizontally monotonic, so (1) is trivially true. For the two
latter cases, the statement is true because $\delta_{h}$ lies above
$\delta_{t}$ in (A4) and $P_{1}$ lies above $P_{3}$ in (C2).

(2) holds because if there are two segments of $\partial C_{1}\setminus\Gamma$
(or $\partial C_{2}\setminus\Gamma$) that form a crossing, then those two
segments also lie and form a crossing on $\partial C$, which contradicts the
assumption that $C$ is a structured container.

(3) holds because $\operatorname{int}(\ell)\subseteq\operatorname{int}(C)$.

To show (4), let $\gamma$ be a fence in $C$. If $\gamma$ lies only on the top
or bottom of one polygon $P\in\operatorname{OPT}(C)$ then a crossing between
$\gamma$ and $\partial C$ implies that $\partial C$ to intersect $P$. However,
$P$ is protected in $C$ by $\gamma$, which is a contradiction. If $\gamma$
lies on top or bottom of two polygons $P,P^{\prime}$ such that $P$ sees
$P^{\prime}$ and one of them is protected in $C$, then $\gamma$ and $\partial
C$ must overlap on $e_{1}(P)\cap e_{d+1}(P^{\prime})$. However, this implies
that $P$ lies inside $C$ and $P^{\prime}$ lies fully outside $C$ or vice-
versa, which is not possible: either both $P$ and $P^{\prime}$ lie inside $C$
or one of them is intersected by a cutting line of $C$.

######  Claim 7.

The polygons $C_{1}$ and $C_{2}$ partition $C$.

For any $C^{\prime}\in\\{C,C_{1},C_{2}\\}$ and any point $w\notin\partial C$,
let $g_{w}$ be the vertical line with $w\in g_{w}$, let $w_{C^{\prime}}^{h}$
($w_{C^{\prime}}^{t}$) be the lowest (highest) point on $\partial
C^{\prime}\cap g_{w}$ strictly above (below) $w$. Let also
$f_{C^{\prime}}^{h}$ ($f_{C^{\prime}}^{t}$) be a fence on $\partial
C^{\prime}$ with $w_{C^{\prime}}^{h}\in f_{C^{\prime}}^{h}$
($w_{C^{\prime}}^{t}\in f_{C^{\prime}}^{t}$). Notice that for every
$w\in\operatorname{int}(C)$, $w_{C}^{h}$ and $w_{C}^{t}$ exist and $f_{C}^{h}$
($f_{C}^{t}$) is oriented from right to left (left to right). We also have
$\operatorname{int}(\overline{w_{C^{\prime}}^{h}w_{C^{\prime}}^{t}})\subseteq\operatorname{int}(C^{\prime})$.
We now argue that for every point $w\in\operatorname{int}(C)\setminus\Gamma$,
we have that

  1. (1)

$w_{C^{\prime}}^{h}$ and $w_{C^{\prime}}^{t}$ exist.

  2. (2)

$f_{C^{\prime}}^{h}$ is oriented from right to left and $f_{C^{\prime}}^{t}$
is oriented from left to right.

for either $C^{\prime}=C_{1}$ or $C^{\prime}=C_{2}$ (but not both). Notice
that since $\partial C_{1}\cup\partial C_{2}=\partial C\cup\Gamma$ by
construction, for any point $w\in\operatorname{int}(C)\setminus\Gamma$,
$w_{C^{\prime}}^{h}$ and $w_{C^{\prime}}^{t}$ must exist for either
$C^{\prime}=C_{1}$ or $C^{\prime}=C_{2}$. We argue case by case.

(A1).

For any $w\in\operatorname{int}(C)\setminus\Gamma$, we have
$g_{w}\cap\Gamma=\emptyset$. Notice also that $f_{1}$ is oriented from right
to left and $f_{2}$ is oriented from left to right. In particular, for any
$w\in\operatorname{int}(C)\setminus\Gamma$, we have (1) and (2) for
$C^{\prime}=C_{2}$ if and only if $w_{C}^{h}\in f_{1}$, $w_{C}^{t}\in f_{2}$
and $w$ lies on the left of $\Gamma$, and (1) and (2) for $C^{\prime}=C_{1}$
otherwise.

(A2).

Assume $p_{t}\in f_{j}$, $j\geq 3$, so $f_{j}$ is oriented from left to right.
Notice that $t(f_{j})$ as well as $h(f_{i}),t(f_{i})$ for $2\leq i\leq j-1$,
lie on the left of $\overline{hp_{t}}$ and below $\gamma_{h}$.

First assume that $w_{C_{1}}^{t}$ exists, so either
$w_{C_{1}}^{t}=w_{C}^{t}\in f_{i}$, $i\geq j$ or $i=1$, or
$w_{C_{1}}^{t}\in\gamma_{h}$. Either way, $w$ lies above or on the right of
$\gamma_{h}$, and in the latter case, so we have $w_{C_{1}}^{h}=w_{C}^{h}\in
f_{i}$ for $i\geq j+1$ or $i=1$. and thus (1). We have that
$f_{C_{1}}^{h}=f_{C}^{h}$ is oriented from right to left (since (2) must hold
for $C^{\prime}=C$), and $f_{C_{1}}^{t}=f_{C}^{t}$ is oriented from right to
left; for the same reason if $w_{C_{1}}^{t}=w_{C}^{t}$, and because
$f_{C_{1}}^{t}=\gamma_{h}$ is oriented from left to right otherwise. This
confirms (2) if $w_{C_{1}}^{t}$ exists.

Assume now that $w_{C_{2}}^{t}$ exists, so
$w_{C_{2}}^{t}=w_{C}^{t}\in\bigcup_{2\leq i\leq j}f_{i}$. If
$w_{C}^{h}\in\partial C_{2}$, we have $w_{C_{2}}^{h}=w_{C}^{h}$ and the claim
is clear. Otherwise, $\operatorname{int}(\overline{w_{C}^{h}w_{C}^{t}})$
crosses $\gamma_{h}$ so $w_{C_{2}}^{h}\in\Gamma^{-}$ and (1) and (2) hold for
$C^{\prime}=C_{2}$, since $\Gamma^{-}$ is oriented from right to left.

(A3).

Assume that $P_{h}$ is protected from the right and without loss of generality
$j=5$. Notice that $\Gamma$ is horizontally monotone. If $w$ lies above
$\Gamma$, then $w_{C}^{h}\in f_{1}\cup f_{5}$, therefore
$w_{C_{1}}^{h}=w_{C}^{h}$ and $w_{C_{1}}^{t}\in\Gamma$ exist, which confirms
(1). Since $\Gamma=\gamma_{h}$ is oriented from left to right and $f_{1}$ and
$f_{5}$ are oriented from right to left, (2) holds as well. The same argument
can be used if $w$ lies below $\Gamma$.

(A4).

Let $j\in[\kappa^{\prime}]$ such that $P_{t}$ is protected via $s_{j}$. We
make a similar observation as in the argument of (A2): $f_{j}$ is oriented
from left to right, $t(f_{j})$, $h(f_{5})$ as well as $h(f_{i}),t(f_{i})$ for
$i\in[j-1]$, lie on the left of $\overline{p_{h}p_{t}}$. Therefore, we can
apply the same idea as for (A2): if $w_{C_{1}}^{t}$ exists, we have
$w_{C_{1}}^{h}=w_{C}^{h}\in\bigcup_{i\geq j+1}f_{i}$ or
$w_{C_{1}}^{h}\in\delta_{t}$, which fulfils (1). (2) holds because $f_{C}^{h}$
and $\delta_{t}$ are oriented from right to left and $f_{C}^{t}$ and
$\delta_{h}$ are oriented from left to right.

If $w_{C_{2}}^{t}$ exists, then either $w_{C}^{h}$ lies on the left of $s_{1}$
and so $w_{C_{2}}^{h}=w_{C}^{h}\in\bigcup_{i\leq j-1}$ or
$\operatorname{int}(\overline{w_{C}^{h}w_{C}^{t}})$ crosses $\delta_{h}$ so
$w_{C_{2}}^{h}\in\Gamma^{-}$. Either way, this implies (1). (2) is then simple
to verify.

(A5).

Same argument as for (A2).

(B1).

Same argument as for (A3).

(B2).

The argument reduces to the cases (A1) to (A5).

(C1).

Same argument as for (A1).

(C2).

Assume first that $P_{3}$ exists and that $s_{1}$ lies on the right of
$s_{2}$. Clearly, for any $w\in\operatorname{int}(C)\setminus\Gamma$, we have
(1) and (2) for $C^{\prime}=C_{2}$ if and only if $w$ lies on the right of
$s_{2}$, on the left of $\ell$ and (strictly) between $f_{1}$ and
$\mu_{3}^{\prime}$ and (1) and (2) hold for $C^{\prime}=C_{1}$ otherwise. The
argument is similar if both $P_{1}$ and $P_{3}$ exist (substitute $f_{1}$ by
$\mu_{1}^{\prime}$).

(C3).

The argument reduces to the cases (A1) to (A5).

Instances with $\kappa\leq 4$. We conclude the proof of the partitioning lemma
by discussing instances with $\kappa\leq 4$. For $\kappa=4$ and $\kappa=3$, we
adhere to the construction of $\Gamma$ for $\kappa=5$ above. The case analysis
is identical as for $\kappa=5$, except that some cases cannot occur (for
example, $\kappa^{\prime}=2$ rules out (A4)).

For $\kappa=2$, we define $P_{0},h,t,p_{h},p_{t}$ as above, except that
$P_{0}$ is now protected via $s_{1}$ (since $s_{2}$ must be a right cutting
line). If we have $\gamma_{h}=f_{1}$ and $\gamma_{t}=f_{2}$, since
$|\operatorname{OPT}(C)|\geq 2$ by assumption, this means that there is a
polygon $P_{0}^{\prime}\in\operatorname{OPT}(C)$ that touches $s_{1}$ and sees
$P_{0}$, so we can set $\Gamma=e_{1}(P_{0}^{\prime})\cap e_{d+1}(P_{0})$ and
thus $\partial C_{1}=\partial P_{0}^{\prime}$ and $\partial C_{2}=\partial
P_{0}$. Otherwise, we construct $\Gamma$ as before (again by substituting
$s_{2}$ with $s_{1}$ and $s_{j}$ with $s_{2}$ for $j\neq 2$).

Lastly, the proofs of Claim 5, Claim 6 and Claim 7 are essentially independent
of $\kappa$ and can be easily be adapted and verified for instances with
$\kappa\leq 4$.