Crossing and Independent Families Among Polygons

Our first result concerns the classical complexity of finding maximum crossing and independent families. For both problems, we demonstrate that they are $\mathrm{𝖭𝖯}$-hard even when all polygons are as simple as possible, namely triangles. Our reductions are from finding a maximum clique and independent set, respectively, in segment intersection graphs [7, 14]. The main idea of the reduction is to “emulate” each segment of the given segment intersection graph using the endpoints of special triangles. And while the principal logic of the reduction can be explained in a streamlined fashion, the underlying gadgets require a careful construction and the precise placement of every triangle. Especially, it is necessary to find a placement of only triangles such that the vertices responsible for the “emulation” of the segment do not interact with gadgets representing other segments.

To overcome the complexity-theoretic intractability of these problems we turn to the tools of parameterized algorithms. We consider the parameterized problems of finding a largest crossing or independent family among a set of $k$ simple polygons, choosing $k$ as our parameter. For parameterized problems whose unparameterized versions are $\mathrm{𝖭𝖯}$-hard the most desirable runtime behavior of an algorithm is of the form $𝒪(f(k)\cdot n^c)$ for some computable function $f$, i.e., a fixed-parameter algorithm. Allowing for more running time, we also consider so-called $\mathrm{𝖷𝖯}$-algorithms where the running time may be in $𝒪(n^{f(k)})$.

As our first algorithmic result, we show that under this parameterization the problem of finding a largest crossing family indeed admits a fixed-parameter algorithm. For this, we consider the segments in a solution ordered by their slopes, together with the polygons on which the segment endpoints lie. Crucially, we argue that this sequence can in fact be viewed as a sequence of what we call bundles which are sets of segments that are consecutive in the sequence and are between a pair of two (not necessarily distinct) polygons. We show that the length of this sequence of bundles is bounded in the number of polygons, which allows us to efficiently branch on the order of pairs of polygons associated with the sequence of bundles. We use the resulting sequence as basis of a dynamic programming approach in which we look at one bundle at a time and compute and tabulate a best option for each last segment (delimiter) of the bundle. We show that it is possible to do that only looking at such tabulated information of the previous bundle and the branched information. The main challenge here is that choices made for a bundle that are compatible with preceding bundles may not be compatible with later bundles or segments in them; carefully filtering our choices without missing a potential solution, we can guarantee that this does not happen.

Turning to our second algorithm, we first realize that for independent families, the above mentioned result by Pilz et al. [21] indicates that the problem is already $\mathrm{𝖭𝖯}$-hard for one polygon, ruling out the existence of even an $\mathrm{𝖷𝖯}$-algorithm. Crucial to their reduction is the fact that segments may appear on the outside and the inside of the polygon. Consequently, we consider the case when segments may only appear on one side of each polygon. We give an $\mathrm{𝖷𝖯}$-algorithm solving this case, again with the number $k$ of polygons on the input as the parameter. The idea is to partition a hypothetical solution into $𝒪(k^2)$ independent parts, each of which is bounded by two segments of the solution. Branching over which segments act as these boundaries allows us to solve the instance by leveraging polynomial-time algorithms for finding maximum independent sets in circle graphs.

Let ${\mathrm{\Pi }}_r$ (${\mathrm{\Pi }}_l$) be the sequence of polygons that arises when picking only the first (resp. second) elements of the classes in $\mathrm{\Pi }$. Since no two polygons intersect each other and no polygon intersects a segment in the crossing family, neither of these sequences contains a subsequence of the form $PQPQ$ with polygons $P\ne Q$. Indeed, two segments that cross and have one of their endpoints in $P$, together with the boundary of $P$, define a bounded region. Polygon $Q$ can either lie inside it or outside it, but not both.

This lack of $PQPQ$ subsequences implies that ${\mathrm{\Pi }}_r$ and ${\mathrm{\Pi }}_l$ are Davenport-Schinzel sequences of order 2 on the $k$ polygons, and their length is therefore at most $2k-1$ [9]. In the combined sequence $\mathrm{\Pi }$, two consecutive classes differ in at least one of the polygons. As there are at most $2k-2$ changes in each of the two sequences of polygons, there are at most $2\cdot (2k-2)=4k-4$ changes in $\mathrm{\Pi }$. Therefore, $\mathrm{\Pi }$ has length at most $4k-3$. $◀$

We now describe our algorithm, which on a high level works by dynamically computing the largest crossing family of a consecutive sequence of bundles with specific first and last segments under the condition that the crossing family is consistent with the selected $\mathrm{\Pi }$.

We precompute which pairs of vertices of polygons see each other (without crossing any polygon boundary). These are the $𝒪(n^2)$ valid segments and they can trivially be computed in $𝒪(n^3)$ time.

In the next step of the algorithm, we guess the sequence $\mathrm{\Pi }$ for a solution of MaxCrossingFamily, that is, we run the algorithm for each possible sequence $\mathrm{\Pi }$. This fixes the order of the bundles and also determines the subset of polygons that contribute to the solution. We call them the contributing polygons, ${𝒫}^{\prime }$. By Lemma 3 and the fact that there are $k$ different polygons, we have at most $k^{2(4k-3)}$ possibilities for $\mathrm{\Pi }$.

For a crossing family, the extreme delimiters $d_0$ (start delimiter) and $d_{\mathrm{\ell }}$ (end delimiter) are the segments with maximum and minimum slopes, respectively. We branch on $d_0$ in a solution. For a class $K_i$, let $|K_i|$ denote the product of the number of vertices of the two polygons in class $K_i$. Since $d_0$ must be in the first class $K_1$ of $\mathrm{\Pi }$, the number of choices is bounded by $|K_1|$. In the worst case, this is $𝒪(n^2)$.

Thus, we run the algorithm in the next step at most $𝒪(n^2{k}^{2(4k-3)})$ times and select the largest crossing family computed among them.

The key information for the solution are the extreme segments for each bundle. A crossing family $C$ respects a sequence of classes $\mathrm{\Pi }$ if the compressed sequence of classes of the segments of $C$ sorted by decreasing slope is $\mathrm{\Pi }$. For a crossing family $C$ that respects $\mathrm{\Pi }$ and for a bundle $B_i$, the delimiter $d_i$ of $B_i$ in $C$ is the segment of $C$ in $B_i$ that has the smallest slope. For notational convenience, we preface the sequence of classes $\mathrm{\Pi }$ by class $K_0$, which is equal to $K_1$. We refer to the resulting extended sequence as ${\mathrm{\Pi }}^{+}$​. We say that the bundle and delimiter of $K_0$ is the start delimiter $d_0$.

Given two segments $a$ and $b$ we say that a point $p$ lies (strictly) between them if $p$ lies in the (open) region bounded by the supporting lines of $a$ and $b$ that does not contain any vertical ray, the horizontal double wedge of $a$ and $b$. (We call the (open) interior of the complement of a horizontal double wedge the vertical double wedge.) We say that a segment $c$ is between $a$ and $b$ if both endpoints of $c$ are between $a$ and $b$, one in each side of the horizontal double wedge. Note that then all the segments of $C$ between two consecutive delimiters $d_i$ and $d_{i+1}$ together with $d_{i+1}$ (and $d_0$ if $d_0=d_i$) form the bundle $B_{i+1}$. We also say that a polygon lies between $a$ and $b$ if all its vertices lie strictly between $a$ and $b$, on the same side of the horizontal double wedge.

We now outline the procedure of our dynamic programming algorithm. Given a set $𝒫$ of polygons, a sequence of classes $\mathrm{\Pi }$, and a segment $d_0$, we aim to find a largest crossing family $C$ among $𝒫$ that respects $\mathrm{\Pi }$ and begins with delimiter $d_0$. For this, we dynamically find an optimal sequence of bundle delimiters. Our algorithm processes the classes in the order given by $\mathrm{\Pi }$. When processing class $i\in [1,\mathrm{\ell }]$, we assume that we have solved the subproblems for every valid delimiter $d_{i-1}$ in class $K_{i-1}$, and that these solutions are stored in a table with one row per delimiter $d_{i-1}$. In that row we store the maximum possible size $|C_{i-1}(d_0,d_{i-1})|$ of a crossing family between (i.e., with extreme delimiters) $d_0$ and $d_{i-1}$. With possible we here mean that at each step we already take into account that we will need to complete the crossing family to one that respects $\mathrm{\Pi }$. This table also includes in each row an iteratively built crossing family with extreme delimiters $d_0,d_{i-1}$, for convenience of solution reconstruction.

At the beginning of the algorithm, the table only contains one row for delimiter $d_0$, with size $1$ and sequence $d_0$. In step $i$ this table gets updated to one that contains the maximum possible size of a crossing family between $d_0$ and $d_i$, $|C_i(d_0,d_i)|$, for each valid delimiter $d_i$ in class $K_i$. We calculate the values $|C_i(d_0,t)|$ for each $t$ in class $K_i$ from the previously tabulated values $|C_{i-1}(d_0,s)|$ with $s$ in class $K_{i-1}$. At step $i$ we compute, for each possible pair $s,t$ of delimiters of classes $K_{i-1}$ and $K_i$, respectively, the best possible crossing family extension $C_i(s,t)$ consisting of segments of class $K_i$ between delimiters $s$ and $t$, not including $s$. We denote its size as $|C_i(s,t)|$. In this computation, we take into account that the final sequence needs to respect $\mathrm{\Pi }$. Also, not all $(s,t)$ pairs are possible: they need to cross and be sorted by slope, but also $t$ should cross the sequence of previous delimiters of $s$. Crucially, by checking certain necessary conditions, we can make this check independent of the sequence of previous delimiters of $s$. This restricts the sizes at each step and disallows certain delimiters (which we mark as having size $-\mathrm{\infty }$). With the above notation, for each $t$ in class $K_i$,

In this way, our algorithm assigns to each delimiter $t$ in class $K_i$ with $i\ge 1$ a delimiter $s$ in the previous class $K_{i-1}$. To obtain the crossing family in the row corresponding to $t$, we take the one corresponding to $s$ and append $C_i(s,t)$.

In the final step of the algorithm, we select a delimiter $d_{\mathrm{\ell }}$ that maximizes $|C_{\mathrm{\ell }}(d_0,d_{\mathrm{\ell }})|$; the corresponding crossing family is stored in the last table in the row for $d_{\mathrm{\ell }}$.

The next lemma specifies how we compute each value $|C_i(s,t)|$, for $s$ and $t$ in classes $K_{i-1}$ and $K_i$, respectively, and the underlying crossing family $C_i(s,t)$. Moreover, it shows that such a crossing family is optimal if $s$ and $t$ are the delimiters of the corresponding classes. In particular, all other segments in a crossing family respecting $\mathrm{\Pi }$ will cross them.

In our algorithm we use Lemma 4 with $𝒬$ equal to the contributing polygons of ${\mathrm{\Pi }}^{+}$ (same as of $\mathrm{\Pi }$). The motivation behind Condition iii and the condition involving $𝒬$ in the second part of the statement is that no segments in a solution crossing family can define a region enclosing a contributing polygon. If such a region existed, there would be three segments defining a triangular region enclosing the polygon, which cannot be the case since any segment incident to an endpoint inside the region can only cross two of the segments.

We first check whether Condition $\star$ holds in $𝒪(n)$ time. If Condition $\star$ does not hold and $𝒬$ is the set of contributing polygons of $\mathrm{\Pi }$, $d_i$ and $d_{i+1}$ cannot be delimiters for classes $K_i$ and $K_{i+1}$.

Let $𝒮$ be the set of segments containing each segment $s\ne d_i,d_{i+1}$ such that $\{d_i,d_{i+1},s\}$ are a crossing family that fulfills Conditions i, ii, and iii. Whether a segment lies in $𝒮$ can be tested in $𝒪(n)$ time per segment $s$ and there are at most $𝒪(n^2)$ such segments. The segments in $𝒮$ form a circle graph, since their endpoints lie either on the boundaries of two disjoint polygons, or on the boundary of one polygon. Consequently, a maximum crossing family $C^{-}$ consisting of segments in $𝒮$ is a clique in this graph and can be computed in time $𝒪({|𝒮|}^2)$ [3]. Let $C$ be the crossing family $C^{-}\cup \{d_i,d_{i+1}\}$, which we computed in $𝒪(n^4)$ time.

We now show that the algorithm above computes the crossing family $C$ as per the lemma statement. First, note that by definition of $𝒮$, Conditions i and ii hold. In the definition of $𝒮$, we only checked that Condition iii holds for triangular regions bounded by segments $d_i$ and $d_{i+1}$. We show that this implies that it also holds for any other triple of segments in $C$.

Assume for contradiction that a polygon $Q\in 𝒬$ lies in a triangular region bounded by three segments in $C$. By Condition $\star$, $Q$ must lie either above the supporting lines of $d_i$ and $d_{i+1}$, or below both. Being in such a bounded region implies that it lies below or above (respectively) the supporting line of a segment $x\in 𝒮$. In both cases, $Q$ lies in the triangle bounded by $x$, $d_i$, and $d_{i+1}$, which we checked is not the case when we included $x$ in $𝒮$.

For the second part of the lemma, consider a crossing family $X$ among $𝒫$ that respects ${\mathrm{\Pi }}^{+}$, no polygon in $𝒬$ lies between consecutive delimiters or in a bounded cell, and has delimiters $d_i$ and $d_{i+1}$ for the bundles of classes $K_i$ and $K_{i+1}$, respectively. Let $C^{\prime }$ be the set of segments of $X$ between $d_i$ and $d_{i+1}$. For each segment $y\in C^{\prime }$ it must hold, by definition, that $\{d_i,d_{i+1},y\}$ is a crossing family satisfying Conditions i, ii, and iii. Thus, $C^{\prime }\subseteq 𝒮$ and replacing $C^{\prime }$ by $C^{-}$ does not decrease the size of the crossing family.

We next show that all segments in $X\setminus C^{\prime }$ cross all the segments in $C^{-}$; refer to Figure 3 (left). This is trivially true for $d_i$ and $d_{i+1}$. Consider a different such segment $z$ in $X$. By definition, $z$ cannot lie between $d_i$ and $d_{i+1}$. Moreover, none of its endpoints can lie between $d_i$ and $d_{i+1}$ since $z$ must cross both $d_i$ and $d_{i+1}$. Thus, by construction of $𝒮$, and concretely Condition iii, no endpoint of $z$ can lie in a triangle bounded by $d_i$, $d_{i+1}$, and a segment in $C^{-}$. This implies that one endpoint of $z$ lies below the supporting line of each segment in $𝒮$ and the other above. Since $z$ crosses $d_{i+1}$ and no segment in $X$ can cross the boundary of a polygon, no endpoint of a segment in $C^{-}$ can lie in a triangle bounded by $z$, $d_i$, and $d_{i+1}$. As the segments in $C^{-}$, by definition, lie between $d_i$ and $d_{i+1}$, this means that every such segment has one endpoint on either side of $z$. We can therefore conclude that $z$ crosses all segments in $C^{-}$.

By construction and Conditions i and ii, after replacing $C^{\prime }$ by $C^{-}$ ${\mathrm{\Pi }}^{+}$ is still respected. It remains to prove that no polygon $Q\in 𝒬$ lies in a bounded cell. By Condition $\star$, $Q$ cannot lie in the horizontal double wedge of $d_i,d_{i+1}$. Assume w.l.o.g. that it lies in the top region of the vertical double wedge of $d_i,d_{i+1}$. If $Q$ lies below the supporting line of a segment in $C^{-}$, then that segment together with $d_i$ and $d_{i+1}$ would contradict Condition iii; see Figure 3 (middle). But if it lies above the supporting lines of all segments in $C^{-}$ then $Q$ can only lie in a bounded cell if it already was in $X\setminus C^{\prime }$, contradicting the assumption of $X$. $◀$

In our algorithm, when computing $C_i(s,t)$ using Lemma 4, if Condition $\star$ does not hold we do not allow such a pair of delimiters (we can return an empty set and size $-\mathrm{\infty }$). The next lemma establishes the correctness of our procedure.

Assume first that a solution exists, and let $d_0,d_1,\mathrm{\dots }{d}_{\mathrm{\ell }}$ be its sequence of delimiters sorted by decreasing slope. Any two consecutive delimiters (together with $d_0$) must fulfill Condition $\star$ in Lemma 4, and thus our algorithm considered them and a largest crossing family between them, since all conditions are necessary. In particular, by Observation 5 Condition iii must hold for the set of contributing polygons. It might be that our algorithm picks a different sequence of delimiters or crossing family between them than the one in the solution assumed, but it will output an at-least-as-large crossing family.

In the other direction, assume that our algorithm produced a crossing family. We want to show that it is indeed a valid crossing family that respects ${\mathrm{\Pi }}^{+}$ and has as start delimiter $d_0$. We construct the extended sequence of classes ${\mathrm{\Pi }}^{+}$ from $\mathrm{\Pi }$ and $d_0$. The computed crossing family corresponds to a sequence of delimiters $d_0,d_1,\mathrm{\dots }{d}_{\mathrm{\ell }}$. If those would indeed form a crossing family sorted by decreasing slope that respects ${\mathrm{\Pi }}^{+}$ and has as start delimiter $d_0$, then by the second part of Lemma 4, the whole crossing family computed would be valid. The sequence of delimiters is sorted by decreasing slope and has as start delimiter $d_0$ by Condition $\star$ at each step. It also respects ${\mathrm{\Pi }}^{+}$ by Condition ii.

It remains to prove that all the delimiters pairwise cross. Assume for contradiction that they do not, and let $d_{i+1}$ be the first delimiter in the sequence that does not cross all the previous delimiters. Thus, $d_0,d_1,\mathrm{\dots },d_i$ form a crossing family. By Condition $\star$, $d_0$, $d_i$, and $d_{i+1}$ are sorted by decreasing slope and there is no contributing polygon between $d_i$ and $d_{i+1}$. In particular, the endpoints of $d_{i+1}$ lie in the top and bottom region of the vertical double wedge of $d_i$ and $d_0$, see Figure 3 (right). In contrast, delimiters $d_1,\mathrm{\dots },d_{i-1}$ have their endpoints in the left and right region of the horizontal double wedge of $d_i$ and $d_0$. Since we only consider valid segments as delimiters and there is no contributing polygon between $d_i$ and $d_{i+1}$, there is no endpoint of the delimiters $d_1,\mathrm{\dots },d_{i-1}$ enclosed by $\{d_0,d_i,d_{i+1}\}$. Thus, $d_0,d_1,\mathrm{\dots },d_{i+1}$ form a crossing family, contradicting the assumption. $◀$

Let ${\mathrm{\Pi }}_i^{+}=(K_0=K_1,\mathrm{\dots },K_{\mathrm{\ell }})$ be the extended sequence of classes of $\mathrm{\Pi }$ and let $𝒬$ be the set of contributing polygons of $\mathrm{\Pi }$. We prove by induction on $i$ that our algorithm computes (in step $i$) a largest crossing family $C$ among $𝒫$ that respects the extended sequence ${\mathrm{\Pi }}_i^{+}=(K_0=K_1,\mathrm{\dots },K_i)$, has as start delimiter $d_0$, as end delimiter a given segment $d_i$ (of class $K_i$) and the following property: ($\diamond$) there is no polygon in $𝒬$ that lies between the extreme delimiters of $C$ or in a triangular region bounded by three segments of $C$. Note that condition ($\diamond$) is necessary to obtain a crossing family fulfilling the conditions of the lemma.

The induction base trivially holds for $i=0$ and by Lemma 4, case $i=1$ also holds. Assume the induction hypothesis for step $i$, and assume for contradiction that in step $i+1$ there is a larger crossing family $C^{\prime }$ that respects ${\mathrm{\Pi }}_{i+1}^{+}$, has as start delimiter $d_0$, as end delimiter $d_{i+1}$, and fulfills ($\diamond$). Let $d_i^{\prime }$ be the previous delimiter in $C^{\prime }$; it might not coincide with the one chosen by our algorithm, but, for a similar argument as in Lemma 6, it is in the table at the start of step $i+1$. By the induction hypothesis, until $d_i^{\prime }$ the crossing family computed and tabulated by our algorithm cannot be smaller than the one of $C^{\prime }$ until $d_i^{\prime }$. Moreover, by Lemma 4, between delimiters $d_i^{\prime }$ and $d_{i+1}$ our algorithm computes a largest crossing family that can replace the one of $C^{\prime }$ while maintaining its properties (respects ${\mathrm{\Pi }}_{i+1}^{+}$, has as start delimiter $d_0$, as end delimiter $d_{i+1}$, and fulfills ($\diamond$)). Thus, the crossing family that our algorithm computes for $d_{i+1}$ in step $i+1$ is at least as large as $C^{\prime }$; contradiction.

This implies that in the last step our algorithm computes a largest crossing family for each possible end delimiter. Lemma 6 ensures that we will succeed, and assuming we chose the end delimiter yielding a largest crossing family, the statement follows. $◀$

We are now ready to establish our first algorithmic result:

Given a set $𝒫$ of polygons, consider a crossing family $C^{\prime }$ solving MaxCrossingFamily. In our branching step, we consider all possible sequences of classes and start delimiters. In particular, the sequence of classes $\mathrm{\Pi }$ and the start delimiter $d_0$ of $C^{\prime }$. By Lemmas 6 and 7, Step 2 in our algorithm computes a largest valid crossing family $C$ with $|C|\ge |C^{\prime }|$ respecting $\mathrm{\Pi }$ and with start delimiter $d_0$, thus solving MaxCrossingFamily.

The algorithm runs in time $f(k)\cdot n^{𝒪(1)}$ where $n$ is the number of vertices of $𝒫$. The precomputation step takes $𝒪(n^3)$ time. We run the polynomial (in $n$ and $k$) algorithm in Step 2 $𝒪(n^2{k}^{2(4k-3)})$ times. Without trying to optimize its running time, it comprises at most $4k-3$ steps corresponding to the classes, and in each step we consider at most $𝒪(n^4)$ pairs of delimiters (assuming that we choose the 4 endpoints of the delimiters from all $n$ points). For each such pair, the procedure in Lemma 4 takes $𝒪(n^4)$ time. $◀$

We can assume a partition into bunches of a maximum independent family of segments between the holes according to Lemma 10, and branch in $n_{}^2{}_{}{}^{𝒪(k^2)}$ ($n$ denotes the overall number of polygon vertices) ways on the boundaries of the corresponding bunches: we branch on a set of $𝒪(k^2)$ pairwise independent delimiting segments, on $𝒪(k^k)$ pairings of them, and $𝒪(1)$ hole boundary parts to complete the boundary. Using Theorem 11, we can compute in polynomial time a maximum independent family of segments within each boundary. We return the union of all families computed in this way together with the branched delimiting segments obtained in this way with maximum size.

The described procedure obviously runs in $\mathrm{𝖷𝖯}$-time parameterized by $k$. Further, the returned family of segments is indeed independent: Segments which are in the solution of the same invocation of Theorem 11 are independent by the correctness of Theorem 11. Segments which are in a solution of an invocation of Theorem 11 are independent from all branched on delimiting segments because they are prohibited from crossing the boundary for which they are in the solution and all delimiting segments lie on or beyond that boundary. Further, the boundary for which a segment was in the solution of an invocation of Theorem 11 separates this segment from all segments in solutions of other invocations of Theorem 11. Independence of branched-on delimiting segments is ensured at branching.

A maximum independent family is returned because in some branch, the delimiting segments will coincide with those that exist in a bunch partition of a maximum independent family according to Lemma 10, and any other segments in a bunch can be replaced by an arbitrary maximum independent family of segments in its boundary. $◀$