Geometric Optimization Parameterized by Piercing Complexity

We quantify piercing using two parameters. For two regions $A$ and $B$, we say that $B$ splits $A$ into $k$ pieces if $A\setminus B$ has $k$ connected components. The fragmentation number $f$ is the maximum number of pieces into which any region can be split by another, and the piercing number $r$ is the maximum number of regions that pierce any single region. A collection of regions with fragmentation number at most $f$ and piercing number at most $r$ is called an $(f,r)$-piercing set. The two parameters play different roles: $r$ bounds how many topologically “disruptive” interactions any one region has, while $f$ bounds the damage caused by one such interaction. This is a deliberately modest parameterization. For many simple geometric families, such as axis-parallel rectangles, the fragmentation number is already constant, so the piercing number is the parameter that interpolates between the non-piercing regime and highly piercing instances. We do not claim that these are the only possible parameters, but they are sufficient to recover local-search PTASs and they isolate a structural feature absent from standard measures such as VC-dimension or union complexity. This framework interpolates smoothly between the non-piercing case ($r=0$) and the fully general setting. Our main result, stated informally below, shows that bounded piercing suffices to recover PTASs for fundamental geometric optimization problems. Note that even if $f$ and $r$ are poly-logarithmic in $n$, our results imply QPTASs for the two problems considered in this paper.

Many geometric optimization problems employ idealized shape models: sensor coverage as disks or wedges [39], map labels as rectangles [2], and facility service regions defined by ${\mathrm{\ell }}_p$-norm balls [19]. These models enable elegant algorithms but poorly model realistic scenarios. Non-piercing regions [35] partially address this by allowing highly irregular and non-convex geometric shapes, but the non-piercing requirement is often violated: obstacles may cause sensor regions to pierce one another, labels for intersecting roads can create piercing pairs, and competing service territories may fragment each other. The $(f,r)$-piercing framework should therefore be viewed as a structural, parameterized relaxation of the non-piercing assumption. It applies to instances in which the piercing graph has bounded maximum degree and each piercing has bounded fragmentation; such restrictions can arise from placement rules, design constraints, or simply from the input being only mildly non-piercing. We use these scenarios as motivation rather than as a claim that the piercing number is universally small in practice.

Our results imply improved approximation guarantees for several well-studied geometric problems. Both the Set Cover and Discrete Independent Set problems are APX-hard for axis-parallel rectangles [7]. For the continuous Independent Set problem, polynomial-time constant-factor approximations [31, 17] and a QPTAS [1] are known, while for the Set Cover problem, the best known approximation is $O(\log \text{Opt})$ via $ϵ$-nets [6, 14], which is tight under this framework [34]. We show that for both problems, if the piercing number of the rectangles is constant, then a PTAS exists – something not achievable by existing techniques.

A similar phenomenon arises for points and line segments. LP-based methods yield at best an $O(\log \text{Opt})$-approximation [6, 14], and lower bounds on $ϵ$-nets rule out substantially better guarantees [4]. At the same time, the problem remains APX-hard even for axis-parallel segments [27]. Our results again yield PTASs for both the Set Cover and Discrete Independent Set problems when the piercing number is bounded.

Parameterized algorithm design based on structural measures of the input is an active research direction [12]. Piercing complexity differs fundamentally from existing parameters in that it is purely topological, unlike geometric parameters such as fatness or density, or combinatorial parameters such as VC-dimension, shallow-cell complexity, or treewidth.

Treewidth, even when combined with bounded ply, can be useful for geometric approximation algorithms [28]. However, intersection graphs of $(f,r)$-piercing regions can contain arbitrarily large grid minors even with bounded ply, implying unbounded treewidth. Thus, treewidth and piercing complexity are incomparable.

Har-Peled and Quanrud [22] introduced the notion of low-density intersection graphs, which leads to PTASs for several geometric problems. Their framework, however, relies on a geometric notion of object size, whereas $(f,r)$-piercing is entirely topological, making the two notions incomparable.

Finally, while $(f,r)$-piercing regions may have arbitrarily large union complexity, we show that they nevertheless have shallow-cell complexity linear in $f$ and $r$ (Theorem 3.3). Since shallow-cell complexity alone is insufficient to yield PTASs [22, 7], this demonstrates that piercing complexity captures a distinct structural property that enables efficient approximation schemes.

Our algorithms follow the local-search framework used in earlier work on geometric packing and covering problems. For non-piercing regions, prior work constructs planar supports, and the needed separators follow directly from planarity [35]. With bounded piercing, the corresponding exchange graphs need not be planar. The main technical step is to recover enough sparsity for local search: lens-bypassing operations simplify the arrangement while preserving the relevant coverage conditions and the $(f,r)$-piercing property, and the resulting exchange graph is represented as a bounded-depth intersection graph of connected subgraphs of the planar dual arrangement graph. A Frederickson-style decomposition of this graph then supplies the local pieces used in the PTAS analysis. This is the point at which the proof extends, rather than merely reuses, the non-piercing machinery.

We prove the lemma by induction on $t$. The base case is $t=1$. Since each region of $\alpha \setminus C_1$ shares exactly one side of $C_1$, the number of connected components of $\alpha \setminus C_1$ is $\text{sides}(C_1,\alpha )$. Thus, the lemma holds for $t=1$. Now, suppose that $t\ge 2$ and the lemma holds for smaller $t$. Since the regions $C_1,\mathrm{\cdots },C_t$ are disjoint, we can draw a chord $\sigma$ of $\alpha$ which does not intersect any of the regions in $C_1,\mathrm{\cdots },C_t$ and splits $\alpha$ into two regions ${\alpha }_1$ and ${\alpha }_2$ so that one of the regions $C_i$ lies in ${\alpha }_1$ and remaining inscribed regions lie in ${\alpha }_2$. By the induction hypothesis, the number of connected components in ${\alpha }_1\setminus C_i$ is $m_1=\text{sides}(C_i,\alpha )$ and the number of connected components in ${\alpha }_2\setminus {\bigcup }_{j\ne i}{C}_j$ is $m_2=1+{\sum }_{j\ne i}\left(\text{sides}(C_j,\alpha )-1\right)$. This implies that the number of connected components of $\alpha \setminus {\bigcup }_{j=1}^t{C}_j$ is $m_1+m_2-1$. We have a “$-1$” because the connected components of ${\alpha }_1\setminus C_i$ and ${\alpha }_2\setminus {\bigcup }_{j\ne i}{C}_j$ that have $\sigma$ on their boundaries correspond to the same connected region in $\alpha \setminus {\bigcup }_{j=1}^t{C}_j$. The lemma follows. $◀$

Let $\alpha$ and $\beta$ be two regions whose boundaries intersect. Then, observe that every connected component $C$ of $\alpha \cap \beta$ is an inscribed region of both $\alpha$ and $\beta$ and furthermore $\text{sides}(C,\alpha )=\text{sides}(C,\beta )$.

Since $\text{sides}(C_j,\alpha )=\text{sides}(C_j,\beta )$ for each $j$, it suffices to prove that $\text{frag}(\alpha ,\beta )=1+{\sum }_{j=1}^t\left(\text{sides}(C_j,\alpha )-1\right)$ which follows directly from Lemma 4.2. $◀$

The above lemma implies that $\text{frag}(\alpha ,\beta )=\text{frag}(\beta ,\alpha )$ for any $\alpha ,\beta$. If the boundaries of $\alpha$ and $\beta$ don’t intersect, by definition we have $\text{frag}(\alpha ,\beta )=\text{frag}(\beta ,\alpha )=0$ and if they do then by Lemma 4.3, $\text{frag}(\alpha ,\beta )=\text{frag}(\beta ,\alpha )$.

Let ${𝒞}_i$ be set of connected components of $\alpha \cap {\beta }_i$ which are all inscribed regions of $\alpha$ and let $𝒞={\bigcup }_{i=1}^t{𝒞}_i$. Since the ${\beta }_i$’s are disjoint, the ${𝒞}_i$’s are disjoint sets. The number of connected components in $X$ is the same as the number of connected components in $\alpha \setminus {\bigcup }_{C\in 𝒞}C$ which by Lemma 4.2 is $1+{\sum }_{C\in 𝒞}\left(\text{sides}(C,\alpha )-1\right)$ which is the same as $1+{\sum }_{i=1}^t{\sum }_{C\in {𝒞}_i}\left(\text{sides}(C,\alpha )-1\right)$ $=1+{\sum }_{i=1}^t\left(\text{frag}(\alpha ,{\beta }_i)-1\right)$ by Lemma 4.3. Note that if ${\beta }_i$ does not pierce $\alpha$, then $\text{frag}(\alpha ,{\beta }_i)-1=0$ and therefore does not contribute to the sum above. Thus, if there are at most $r$ regions piercing $\alpha$, and $\text{frag}(\alpha ,{\beta }_i)\le f$ for all $i$, since the ${\beta }_i$ are disjoint, it follows that the number of connected components of $X$ is at most $rf$. $◀$

We now show that applying lens bypassing does not increase the fragmentation number of the arrangement.

We first show that $\text{frag}({\alpha }^{\prime },\beta )\le \text{frag}(\alpha ,\beta )$. To see this, note that the connected components of ${\alpha }^{\prime }\cap \beta$ are the same as those in $\alpha \cap \beta$ except that the lens $L$ we bypassed appears as a connected component in $\alpha \cap \beta$ but not in ${\alpha }^{\prime }\cap \beta$. Since $\text{sides}(L,\alpha )=1$, $L$ does not contribute to the expression for $\text{frag}(\alpha ,\beta )$ in Lemma 4.3. Thus if the boundaries of ${\alpha }^{\prime }$ and $\beta$ intersect, $\text{frag}({\alpha }^{\prime },\beta )=\text{frag}(\alpha ,\beta )$. Even if $\partial {\alpha }^{\prime }$ and $\partial \beta$ don’t intersect, we have $0=\text{frag}({\alpha }^{\prime },\beta )\le \text{frag}(\alpha ,\beta )$.

Now consider any region $\gamma \ne \beta$. The boundary of $L$ consists of an arc ${\sigma }_{\alpha }$ of $\partial \alpha$ and an arc ${\sigma }_{\beta }$ of $\partial \beta$. Since $L$ is a minimal lens, the intersection of $\partial \gamma$ with $L$ consists of disjoint arcs each with one endpoint on ${\sigma }_{\alpha }$ and the other endpoint on ${\sigma }_{\beta }$. Since bypassing $L$ by $\alpha$ effectively moves ${\sigma }_{\alpha }$ to ${\sigma }_{\beta }$ ⁴⁴4more precisely a curve arbitrarily close to it, the intersection of $\alpha$ with $\gamma$ is combinatorially the same as the intersection of ${\alpha }^{\prime }$ with $\gamma$. This implies that $\text{frag}({\alpha }^{\prime },\gamma )=\text{frag}(\alpha ,\gamma )$. $◀$

The Lemma below follows from Frederickson’s decomposition [16].

In order to show that $𝒢$ admits a $({\lambda }_1,{\lambda }_2,{\lambda }_3)$-decomposition, we need to show that for any given parameter $t$ and any graph $G=(V,E)\in 𝒢$ with $m$ vertices, we can obtain $X\subseteq V$ and a partition of $V\setminus X$ into $V_1,\mathrm{\cdots },V_{\mathrm{\ell }}$ satisfying the conditions stated in Definition 2.10.

We obtain the required $X,V_1,\mathrm{\cdots }{V}_{\mathrm{\ell }}$ by applying the result of Frederickson [16] which shows that the family of planar graphs admits a $(c_1,c_2,c_3)$-decomposition for some constants $c_1,c_2,c_3$. Let $H=(U,F)$ be the planar graph with $n=|U|\le \tau m$ s.t. $G$ is the depth $d$ intersection graph of connected subgraphs of $H$. For any $v\in V$, let $C_v$ denote the connected subgraph in $H$ corresponding to the vertex $v$ in $G$. Applying the result of Frederickson [16] with parameter $t^{\prime }=t/d$, we obtain sets $Y\subseteq U$ and a partition of $U\setminus Y$ into $U_1,\mathrm{\cdots },U_{\mathrm{\ell }}$ s.t. $\mathrm{\ell }\le c_2\frac{n}{t^{\prime }}$, $|Y|\le c_{1}n/\sqrt{t^{\prime }}$, $|U_i|\le t^{\prime }\forall i$, $|N_H(U_i)\cap Y|\le c_3\sqrt{t^{\prime }}\forall i$, and $N_H(U_i)\cap U_j=\mathrm{\varnothing }\forall i\ne j$.

Note that $\mathrm{\ell }\le c_{2}d\tau \cdot m={\lambda }_{2}m$ with ${\lambda }_2=c_{2}d\tau$. We next define $X$ as the set of all vertices in $G$ whose corresponding connected subgraph in $H$ contains one of the vertices in $Y$. Since any vertex in $H$ is contained in at most $d$ of the connected components, $|X|\le d\cdot |Y|\le c_1\tau d^{3/2}\cdot \frac{m}{\sqrt{t}}={\lambda }_1\frac{m}{\sqrt{t}}$ with ${\lambda }_1=c_1{d}^{3/2}\tau$. For any $i$, we define $V_i$ as the set of vertices in $G$ whose corresponding connected subgraphs in $H$ only contain vertices from $U_i$. Note that $V_1,\mathrm{\cdots },V_{\mathrm{\ell }}$ is a partition of $V\setminus X$ since for any $v\in V$ note that if $C_v$ does not contain any of the vertices in $Y$, then it can only contain vertices from exactly one group $U_i$ (this relies on the fact that for $i\ne j$, $N(U_i)\cap U_j=\mathrm{\varnothing }$). Since every vertex in $U_i$ can be in at most $d$ connected subgraphs, $|V_i|\le d\cdot |U_i|\le t$. Next, note that $|N_G(V_i)\cap X|\le d\cdot |N_H(U_i)\cap Y|\le c_3\sqrt{d}\cdot \sqrt{t}={\lambda }_3\sqrt{t}$ with ${\lambda }_3=c_3\sqrt{d}$. To see this, note that for any $(v,x)$ s.t $v\in V_i$ and $x\in X$, $C_x$ must contain a vertex of $N_H(U_i)\cap Y$ and each such vertex is contained in at most $d$ connected subgraphs. Finally, $N_G(V_i)\cap V_j=\mathrm{\varnothing }$ since for any $v\in V_i$ and $v^{\prime }\in V_j$, $C_v$ and $C_{v^{\prime }}$ don’t have a vertex in common in $H$ – this follows from the fact that the vertices in $C_v$ are from $U_i$ and the vertices in $C_{v^{\prime }}$ are from $U_j$ and $U_i\cap U_j=\mathrm{\varnothing }$. The lemma follows. $◀$

We now define a two-colored version of an $(f,r)$-piercing regions with additional properties. This will be useful in the analysis of the algorithms in Section 5.

For any special $(f,r)$-piercing set $\mathrm{\Gamma }$, let $I(\mathrm{\Gamma })$ denote the bipartite intersection graph $(\mathrm{\Gamma },E)$ where there is an edge between any intersecting pair of regions of different colors in $\mathrm{\Gamma }$.

We will do a sequence of minimal lens bypassing operations so that for any point $p\in P$ the following coverage condition holds: if $p$ is contained in at least one red and one blue region before the bypassing, it is still contained in at least one red and one blue region after the bypassing. After such simplifications, we will show that the resulting arrangement is a special $(f,r)$-piercing set. Note that in any lens bypassing any region $\gamma$ is either not modified or modified to a region ${\gamma }^{\prime }\subseteq \gamma$. Also, note that by Lemma 4.5, the set of regions remains $(f,r)$-piercing at all times. First, note that upon bypassing any minimal lens formed by two regions of the same color, regardless of the region modified, the coverage condition holds. Therefore we can bypass all such monochromatic minimal lenses. Now consider a bi-chromatic minimal lens formed by a red and a blue region which is contained in a third region (red or blue). We can also bypass such lenses while maintaining the coverage condition by making sure that the region modified during the bypassing is the one whose color matches the third region. After we have bypassed all minimal lenses of the above two types, observe that we cannot have any monochromatic lenses (even non-minimal). To see this, consider a minimal monochromatic lens i.e., a monochromatic lens which does not contain another monochromatic lens. Such a lens is either a minimal lens or it contains a bi-chromatic lens. In the former case, the lens should have been bypassed, and in the latter case, the bi-chromatic lens is contained in a third region and should have been bypassed. This implies that any regions of the same color are either disjoint or are piercing. The lemma follows. $◀$

Since $\mathrm{\Gamma }$ is a special $(f,r)$-piercing set, the arrangement of regions in $\mathrm{\Gamma }$ does not contain any monochromatic lenses and all bi-chromatic lenses are minimal. We repeatedly bypass bi-chromatic minimal lenses formed by regions that also intersect outside the lens as this does not violate the conditions of the lemma. Thus if any lens is left it is the only cell in the intersection of two regions forming it. In particular, the two regions cannot be piercing and they cannot be intersecting in any other lens. $◀$

It suffices to show that the number of intersections of the boundaries of pairs of regions in $\mathrm{\Gamma }$ is $O(r^{2}fn)$. In order to do this, we partition the red regions into $r+1$ sets ${ℛ}_1,\mathrm{\cdots },{ℛ}_{r+1}$ s.t. the regions in each set are disjoint. This is because regions of the same color are either piercing or disjoint and no region is pierced by more than $r$ other regions. Similarly, we partition the blue regions into $r+1$ sets ${ℬ}_1,\mathrm{\cdots },{ℬ}_{r+1}$ s.t. the regions in each set are disjoint. Overall, we have $2(r+1)$ sets of disjoint regions. Consider any two of these families $A$ and $B$ (which may or may not be of the same color).

We next argue that the number of intersections among the regions in $A\cup B$ is $O(rfn)$ where $m=|A|+|B|$. To see this, imagine replacing each region $\alpha \in A$ by the connected components in $\alpha \setminus {\bigcup }_{\beta \in B}\beta$. The number of components any $\alpha$ is split into is at most $rf$ by Lemma 4.4. The overall number of regions now is at most $m^{\prime }=|A|\cdot rf+|B|\le rfm$ which are interior disjoint but certain pairs touch along their boundaries.

Consider the touching graph defined by these regions in which there is a vertex corresponding to each region and two vertices are adjacent iff the boundaries of their corresponding regions overlap in an arc of non-zero length. Note that this graph is planar and hence, the number of edges in this graph is at most $3m^{\prime }$. Here it is important to note also that the touching graph does not have multi-edges due to the assumption that two piercing regions do not form any lenses and two non-piercing regions form at most one lens. Each edge in the touching graph corresponds to two intersection points among boundaries of regions in $A\cup B$, showing that the number of intersections among the regions in $A\cup B$ is at most $3rfm$.

Since each set $A\in 𝒮=\{{ℛ}_1,\mathrm{\cdots },R_{r+1}\}\cup \{{ℬ}_1,\mathrm{\cdots },B_{r+1}\}$ appears in $O(r)$ pairs of the form $(A,B)\in \left(\genfrac{}{}{0pt}{}{𝒮}{2}\right)$ and ${\sum }_{i=1}^{r+1}|{ℛ}_i|+|{ℬ}_i|=n$, the overall number of intersections among the boundaries of regions in $\mathrm{\Gamma }$ is $O(r^{2}fn)$ which in turn implies that the number of cells in the arrangement of regions in $\mathrm{\Gamma }$ is also $O(r^{2}fn)$. $◀$

Consider a special $(f,r)$-set $\mathrm{\Gamma }$. By Lemma 4.11, we can assume without loss of generality, that $\mathrm{\Gamma }$ is a simplified special $(f,r)$-set. By Lemma 4.12, the number of cells in the arrangement of the regions in $\mathrm{\Gamma }$ is $O(r^{2}fn)$ Now consider the dual arrangement graph (Definition 2.4) $H$ of the regions in $\mathrm{\Gamma }$. Note that $H$ is planar and the cells contained in any region $\gamma \in \mathrm{\Gamma }$ correspond to a connected subgraph of $H$. Note also that any cell is contained in at most $r+1$ red regions and at most $r+1$ blue regions and therefore is in at most $2(r+1)$ regions overall. In other words, each graph $G\in ℐ$ is the depth $d=2(r+1)$ intersection graph of connected subgraphs in a planar graph $H$ having at most $\tau n$ vertices where $\tau =O(r^{2}f)$. By Lemma 4.7, $ℐ$ admits a $({\lambda }_1,{\lambda }_2,{\lambda }_3)$-decomposition where ${\lambda }_1=O(d^{3/2}\tau )=O(r^{3.5}f),{\lambda }_2=O(d\tau )=O(r^{3}f)$, and ${\lambda }_3=O(\sqrt{d})=O(\sqrt{r})$. $◀$