Covering and Partitioning Complex Objects with Small Pieces

Let $𝒮=𝒬\cup ℛ$ be the union of the global optimum and the local optimum. Using Lemma 3, we obtain a new set ${𝒮}^{\prime }={𝒬}^{\prime }\cup {ℛ}^{\prime }$ of properly non-piercing pieces and a finite set of points $X$ such that a subset of ${𝒮}^{\prime }$ covers $X$ if and only if the corresponding subset of $𝒮$ covers $P$. Since $𝒬$ and $ℛ$ both cover $P$, ${𝒬}^{\prime }$ and ${ℛ}^{\prime }$ must both cover $X$.

Recall that $q=|𝒬|=|{𝒬}^{\prime }|$ and $r=|ℛ|=|{ℛ}^{\prime }|$. If $r\ge (1+\epsilon )q$ for some $1\ge \epsilon >0$, then by Lemma 1, we can replace a set of at most $C\frac{1}{{\epsilon }^2}$ of the pieces in ${ℛ}^{\prime }$ with a strictly smaller set of pieces from ${𝒬}^{\prime }$ to obtain another cover of $X$. If we swap the corresponding pieces in $ℛ$ with the corresponding pieces in $𝒬$, then we get a small cover of $P$, proving the claim. $◀$

Lemma 2 gives sufficient conditions for a small cover to be a $(1+\epsilon )$-approximation of the optimum. We say that a small cover $R$ is a $k$-local optimum if no set of at most $k$ pieces from $ℛ$ can be replaced by a strictly smaller set of small pieces.

Taking $C$ to be the constant from Lemma 2, let $C^{\prime }=\sqrt{C}$ and $k_0=\lceil C^{\prime }\rceil$. Because $ℛ$ is $k$-local optimum, no set of at most $k$ pieces can be replaced by a smaller set of small pieces. If $r\le k$, then $ℛ$ is necessarily an optimal solution and the claim holds. So suppose that $r>k$. Let $𝒬$ be an optimal small cover of $P$ with $q$ complete pieces. Suppose for contradiction that $r\ge \left(1+\frac{C^{\prime }}{\sqrt{k}}\right)q$. Note that for $\epsilon :=\frac{C^{\prime }}{\sqrt{k}}\le \frac{C^{\prime }}{\sqrt{k_0}}\le 1$, Lemma 2 guarantees a set of $k^{\prime }\le C/{\epsilon }^2=C\frac{k}{C^{\prime 2}}=k$ pieces can be replaced by fewer pieces from $𝒬$. A contradiction to the fact that $ℛ$ is a $k$-local optimum. Hence, . $◀$

Let $A$ and $B$ be realizations of a combinatorial structure with $m$ squares. We show that $A$ is a cover if and only if $B$ is a cover. Suppose that $A$ is a cover. We continuously move the bounding squares from their positions in $A$ to their positions in $B$, along straight lines in the $2m$-dimensional coordinate space. If, during this process, the arrangement stops being a cover, then one of the following cases occurs: (a) part of a polygon edge is uncovered, (b) part of the interior is uncovered, or (c) a piece becomes disconnected. The cases are illustrated in Figure 4.

We consider a snapshot right after the first point becomes uncovered. In case (a), the uncovered region is a triangle (or a rectangle). Note that the intersection of a right angle of this region has changed sides with respect to the polygon side independent of whether both or just one involved square is moving. In case (b), the uncovered region is a rectangle and its appearance is due to two squares that become disjoint due to the movement of at least one square. In case (c), a side of a moving square now intersects a side of the polygon which was previously disjoint. Consequently, in each case some of the combinatorial data is changing. Since the set of realizations of a combinatorial structure is convex, we conclude that this doesn’t happen. Since the arrangement forms a cover at every point in the motion, we conclude that $B$ must be a cover.

By a symmetric argument, it is clear that if $B$ is a cover, then $A$ is a cover. $◀$

Given a cover with complete pieces, we want to check if some set of $k$ of its pieces can be swapped for a set of $k-1$ pieces. This is accomplished by the next lemma.

For each of the $\left(\genfrac{}{}{0pt}{}{m}{k}\right)$ $k$-subsets of $ℛ$, we remove it and test each of the ways of adding $k-1$ squares to the combinatorial arrangement. We need to argue that for any fixed $k$, there are only polynomially many ways of adding $k-1$ squares to a combinatorial structure with $m$ squares. This corresponds to adding $2k$ vertical lines and $2k$ horizontal lines to the arrangement. A line arrangement with $\mathrm{\ell }$ lines contains at most $O({\mathrm{\ell }}^2)$ intersection points. Thus there are $O({\mathrm{\ell }}^2)$ combinatorially different ways to add a new line with a fixed slope. A combinatorial structure with $m$ squares has $n+2m$ lines. So the number of ways of adding the new $4k$ lines is ${𝒪}_k({(n+m)}^{4k})$. The intersection of a square with $P$ can have at most $n$ connected components, so in total there are ${𝒪}_k({(n+m)}^{4k+1})$ ways of adding $k$ squares to the arrangement. For fixed $k$, this is polynomial in $n$ and $m$.

For each of these candidate combinatorial structures, we need to check whether it represents a valid covering. By Lemma 5, it suffices to find a single representative set of pieces (if one exists). Each element of the combinatorial data is a linear constraint involving the coordinates of the squares and either an equality or a strict inequality. We construct an LP instance from these linear constraints, adding a new variable $t$ and replacing each strict inequality $𝒞>0$ with $𝒞\ge t$. To test if a solution exists, we solve the LP instance in which the objective function is to maximize $t$. If there is no feasible solution with $t>0$, then we conclude that there is no valid swap with this combinatorial structure. If we find a feasible solution with $t>0$, then we check if this solution covers all of $P$. We do this by constructing the pieces explicitly and computing their union. If the union does not cover $P$, then we know that no arrangement with this combinatorial structure does. The only free variables in the LP instance are $t$ and the $2(k-1)$ coordinates of the newly-added bounding squares. So in order to solve the LP instance, we can just check all of the ${(n+m)}^{𝒪(k)}$ basic solutions. This takes (strongly-)polynomial time for a fixed $k$.

We should check that this procedure finds a swap if one exists. Suppose that there is a set of $k$ pieces in the initial cover that can be swapped with $k-1$ pieces in order to obtain a new cover ${ℛ}^{\prime }$. The cover ${ℛ}^{\prime }$ has a combinatorial structure, which is one of the candidate structures tested by our procedure. Furthermore, ${ℛ}^{\prime }$ is a realization of this structure with the positions of the $m-k$ old pieces being the same as in $ℛ$, so such a realization exists, and the linear programming step will find one (but the realization found is not necessarily the same one as ${ℛ}^{\prime }$). Since ${ℛ}^{\prime }$ is a cover, by Lemma 5, the realization found will be a cover. $◀$

Fix $k$ such that $\frac{C^{\prime }}{\sqrt{k}}\le \epsilon$, and $k\ge C^{\prime }$, where $C^{\prime }$ is the constant from Corollary 4.

We can construct a cover of $P$ with small pieces by overlaying $P$ with the integer grid and taking the connected components of each intersection. Recall that the intersection of a unit square with $P$ has at most $n$ connected components. Hence, we obtain an initial solution with at most $Dn$ pieces, where $D$ is the number of integer grid squares intersecting $P$. We then check if this cover is a $k$-local optimum using the procedure from Lemma 6.

If this cover is not a $k$-local optimum, then we perform the swap and repeat the process until no more valid swaps remain. Every swap decreases the total number of pieces by $1$, so the algorithm terminates after at most $Dn$ steps, and when it does we have obtained a cover such that no set of $k$ pieces can be swapped for a strictly smaller set of pieces. By Corollary 4, this solution has at most $(1+\epsilon )$-times as many pieces as an optimal solution. It is clear by Lemma 6 that the entire process takes time at most ${(Dn)}^{\text{poly}(\frac{1}{\epsilon })}$. $◀$

The algorithm in Theorem 7 runs in polynomial time on real RAM, but the bit-complexity of the coefficients can grow by a constant factor after each swap, potentially leading to exponential coefficient growth. In order to obtain an algorithm that runs in strongly-polynomial time, we can adjust the coordinates after each swap. Let $m$ be the number of squares of the cover. We consider the LP instance $L$ corresponding to the combinatorial structure of the cover. Here, $L$ has two variables for all $m$ squares, not just the new squares introduced in the latest swap. The cover that we found is a feasible solution $x\in {ℝ}^{2m+1}$ to $L$. There are two coordinates in $x$ for each square and one for the value $t$ in the strict inequalities. We want to find a basic feasible solution to $L$, i.e., a vertex of the polyhedron defined by the constraints, because the bit-complexity of the variables in such a solution is polynomial in $n$, $D$ and the bit-complexity of the coordinates of vertices of $P$. The value of $t$ (the variable for strict inequalities) should still be positive in the new solution.

This can be done in strongly-polynomial time. We can write $L$ such that all constraints have form $𝒞\ge 0$. We start by evaluating each constraint at the feasible solution $x$. A constraint $𝒞\ge 0$ is tight if $𝒞(x)=0$. Let $𝒟$ be the set of tight constraints and let $\mathscr{H}=\{y\in {ℝ}^{2m+1}\mid \forall 𝒞\in 𝒟:𝒞(y)=0\}$. In other words, $\mathscr{H}$ is the affine subspace that causes the tight constraints to be tight. The solution $x$ is a basic feasible solution if $\mathscr{H}$ has dimension $0$. Otherwise, we can find a direction $v\in \text{Vec}(\mathscr{H})$ such that $t$ does not decrease when moving in direction $v$. We move from $x$ in direction $v$ until an additional constraint becomes tight.

We obtain a new feasible solution $x^{\prime }$ to $L$, where $t$ at $x^{\prime }$ is at least as large as $t$ at $x$. Furthermore, the dimension of ${\mathscr{H}}^{\prime }$, the subspace of tight constraints corresponding to $x^{\prime }$, has decreased by at least $1$ compared to $\mathscr{H}$. So we can repeat this process to find a basic feasible solution with the required properties. The number of arithmetic operations depends only on the number of variables and the number of constraints, so this process runs in strongly polynomial time. The bit-complexity of a basic feasible solution is polynomial in $n$, $D$ and the bit-complexity of the coordinates of vertices of $P$. In particular, it does not increase with the number of swaps performed by the algorithm in Theorem 7.

Use Theorem 8 with $𝒜$ being the algorithm of Theorem 7 with $D=O({(n/\epsilon )}^2)$. $◀$

We now sketch the idea of the reduction. We first argue that there is a set of $k=O(n)$ disjoint “large” corridors $𝒞=\{C_1,\mathrm{\dots },C_k\}$ with each $C_i\subset P$ such that we can solve the covering problem on $C_1,\mathrm{\dots },C_k,$ and $P\setminus \bigcup 𝒞$ separately. Each corridor $C_i$ is constructed to have a pair of sides that are either both vertical or both horizontal and are of distance $\ge 1/\epsilon$ apart. The remaining two sides are both contained in an edge of $P$. Finally, each $C_i$ is essentially picked to be of maximum volume satisfying these properties.

We will show that the union of $(1+O(\epsilon ))$-approximate covers of $C_1,\mathrm{\dots },C_k$ and $P\setminus \bigcup 𝒞$ yields a $(1+O(\epsilon ))$-approximate cover of $P$. For $P\setminus \bigcup 𝒞$, the diameter of each connected component is at most $n/\epsilon$, so we can use the algorithm $𝒜$ for bounded diameter polygons. The corridors are more tricky as the size of their optimal solutions cannot be bounded in terms of $n$, so for those, we maintain an implicit solution. Denote by $a_i$ and $p_i$ the area and perimeter of $C_i$. If $a_i\ge p_i/\epsilon$, one can show that the intersection $C_i$ with the integer grid gives an $1+O(\epsilon )$ approximate cover, and this solution is easy to describe implicitly. The tricky part is handling a corridor $C_i$ with $a_i\le p_i/\epsilon$ where $C_i$ is “long” and “skinny”. Suppose that $C_i$ has a pair of vertical edges (the horizontal case is similar). In this case, we partition $C_i$ further into corridor sections ${(S_i^j)}_{j=1}^t$, all having a pair of vertical edges and width $1/\epsilon$. We then again argue that it suffices to solve the problem on each $S_i^j$ with an approximation ratio of $1+O(\epsilon )$. Unfortunately, we cannot afford to find a solution for each $S_i^j$ separately, but we can argue about a certain monotonicity of sizes of optimal covers of the $S_i^j$. Namely, after appropriate translations, it is either the case that $S_i^j\subset S_i^{j+1}$ for all $j$ or it is the case that $S_i^j\supset S_i^{j+1}$ for all $j$. In the former case, we show that the size of the optimal cover of $S_i^j$ is at most the size of the optimal cover of $S_i^{j+1}$ and a similar claim holds in the latter case. Based on these properties, and defining $\mathrm{\ell }={\epsilon }^{4}t$, we show that it suffices to approximate the minimum covers of $S_i^{\mathrm{\ell }},S_i^{2\mathrm{\ell }},\mathrm{\dots }{S}_i^{\lfloor t/\mathrm{\ell }\rfloor \mathrm{\ell }}$. For any $S_i^j$ with , for some $k$, we can then use the size of the approximate cover of $S_i^{(k+1)\mathrm{\ell }}$ as an upper bound on the size of the optimal cover of $S_i^j$. This only requires us to run $𝒜$ on the $t/\mathrm{\ell }=O(1/{\epsilon }^4)$ instances of the form $S_i^{(k+1)\mathrm{\ell }}$. While for some values of $k$, this approach might not give $1+O(\epsilon )$ approximation to $S_i^j$, the monotonicity ensures that for most values of $k$, the approximation is good, and suffices to give a final approximation guarantee of $1+O(\epsilon )$.

Consider an optimal small cover $𝒬$ consisting of complete small pieces; see Figure 5.

Consider the overlay of $𝒬$ and choose a point in the interior of each cell which is also in $P$. Construct a set of proper non-piercing regions ${𝒬}^{\prime }$ as in Lemma 3. As described in the proof, the pieces in ${𝒬}^{\prime }$ are subsets of those in $𝒬$, except that some holes of $P$ have been filled. Importantly, the boundaries of the pieces in ${𝒬}^{\prime }$ are just slight perturbations of those in $𝒬$.

The following process of lens bypassing is described in [34, Section 4]. Since ${𝒬}^{\prime }$ are non-piercing, any intersection $Q_i^{\prime }\cap Q_j^{\prime }$ consists of a set of lenses, which are regions bounded by one interval of the boundaries of each set $Q_i^{\prime }$ and $Q_j^{\prime }$. In the process of lens bypassing, we consider an inclusion-wise minimal lens $\mathrm{\ell }$, say in the intersection $Q_i^{\prime }\cap Q_j^{\prime }$. Let the boundary of $\mathrm{\ell }$ be ${\gamma }_i\cup {\gamma }_j$, where ${\gamma }_i$ and ${\gamma }_j$ are on the boundaries of $Q_i^{\prime }$ and $Q_j^{\prime }$, respectively. We change the boundary of $Q_i^{\prime }$ by replacing ${\gamma }_i$ by a curve following ${\gamma }_j$ (but slightly outside $\mathrm{\ell }$ to avoid non-proper intersections). This effectively removes $\mathrm{\ell }$ from $Q_i^{\prime }$. It is shown [34, Lemma 4.6] that the operation results in a set of regions that are also non-piercing. Repeating the process results in a set ${𝒬}^{\prime \prime }$ of pairwise disjoint regions that are subsets of the original regions ${𝒬}^{\prime }$ and still contain the points $X$.

Consider any hole $H$ of $P$, i.e., $H$ is a bounded connected component in the complement of $P$. Recall that in the pieces ${𝒬}^{\prime }$, the hole $H$ might have been filled in some of them, so $H$ might also be filled in some of the pieces ${𝒬}^{\prime \prime }$. In our modifications from $Q$ to $Q^{\prime \prime }$, we have only ever made modifications along curves that are disjoint from $H$. Hence, for each piece $Q_i^{\prime \prime }\in {𝒬}^{\prime \prime }$, we either have $H\subset Q_i^{\prime \prime }$ ($H$ is filled) or $H\cap Q_i^{\prime \prime }=\mathrm{\varnothing }$ ($H$ is still a hole of $Q_i^{\prime \prime }$ or outside the outer boundary). We can remove $H$ from all pieces where it is filled, thus reintroducing $H$ as a hole, and this will not break connectivity. We do so for all holes of $P$. We end up with regions ${𝒬}^{\prime \prime \prime }$ that are pairwise disjoint and all contained in $P$. Furthermore, the regions ${𝒬}^{\prime \prime \prime }$ still cover $P$ in the sense that each region in the overlay of the original cover $𝒬$ is contained in a region in the overlay of ${𝒬}^{\prime \prime \prime }$, except that the boundary might be slightly perturbed. We can thus create pieces ${𝒬}^{\prime \prime \prime \prime }$ analogous to ${𝒬}^{\prime \prime \prime }$ using the original boundaries, and these pieces will cover all of $P$ and still be pairwise interior-disjoint. We therefore obtain a small partition of $P$. $◀$