Maximum Independent Sets in Disk Graphs with Disks in Convex Position

In this paper, we consider a special setting in which the disks in $𝒟$ are in convex position, meaning that every disk of $𝒟$ contributes to the boundary of the convex hull of $𝒟$ (see Figure 2). Under this assumption, we present an exact algorithm that computes a maximum-weight independent set in $G(𝒟)$ in $O(n^3\log n)$ time. This setting bridges the gap between the general two-dimensional problem and one-dimensional variants such as circular graphs, which admit near-linear-time algorithms [5].

The maximum-weight independent set problem under this convex position assumption has been studied previously, but only for the unit-disk case in which all disks have the same radius [30, 33]; in that setting, the previously best algorithm runs in $O(n^{37/11})$ time [33]. Our algorithm applies to disks of arbitrary radii and, moreover, improves the running time even in the unit-disk case.

We say that a set of disks is in strongly convex position if every disk has a single maximal disk arc appearing on the boundary of the convex hull of all disks (see Figure 2; but the disks in Figure 2 are not in strongly convex position). We solve the problem gradually as follows.

1. 1.

   We first consider a very special case in which the disks of $𝒟$ are in strongly convex position and $𝒟$ has a maximum-weight independent set that is itself strongly convex; we refer to this as the strongly-convex-input-and-output case. Our algorithm for this case is based on dynamic programming and can be viewed as an extension of the unit-disk algorithm of [33] to disks of arbitrary radii. Moreover, we identify a new monotonicity property that allows our algorithm to run faster than the previous unit-disk algorithm [33]. Our algorithm for this case is presented in Section 3.

2. 2.

   We then handle the strongly-convex-input case, in which $𝒟$ is strongly convex but does not necessarily admit a strongly convex maximum-weight independent set. We reduce this case to the first one by adding a set $B$ of $O(n)$ auxiliary points, treated as special disks, such that (i) these special disks appear in any maximum-weight independent set of $𝒟\cup B$, and (ii) for any subset ${𝒟}^{\prime }\subseteq 𝒟$, the set ${𝒟}^{\prime }\cup B$ is strongly convex. This case is discussed in Section 4.

3. 3.

   Finally, we address the most general case in Section 5, where $𝒟$ is not necessarily strongly convex and does not necessarily admit a strongly convex maximum-weight independent set. We reduce this case to the second one by again adding a set of auxiliary points as special disks.

As an application of our independent set algorithm, we also solve a dispersion problem for a set of $n$ disks in convex position: given an integer $k$, the goal is to find a subset of $k$ disks that maximizes the minimum pairwise distance among all disks in the subset, where the distance between two disks is defined as the minimum distance between any point in one disk and any point in the other. Our algorithm for this problem runs in $O(n^3{\log }^{2}n)$ time and is presented in Section 6.

Due to the space limit, many proofs are omitted but can be found in the full paper.

Recent developments in geometric algorithms have demonstrated that the convex position constraint can serve as a powerful structural assumption. For a variety of classical problems, it enables exact polynomial-time algorithms, often by exploiting the inherent cyclic structure induced by convexity.

For example, the $k$-center problem is NP-hard for arbitrary point sets, but becomes polynomial-time solvable when the points are in convex position [11, 33]. Another recent result that exploits convex position concerns dominating sets in disk graphs [33, 31]. Note that for unit-disk graphs, the disk set is in convex position if and only if the centers of the disks are in convex position; this equivalence no longer holds when disks have different radii.

In the literature, related convexity assumptions have also been studied for disk graphs, including settings in which the disk centers are in convex position and settings in which the disks themselves are in convex position. For instance, Herrera and Pérez-Lantero [18] and Huemer and Pérez-Lantero [19] investigate combinatorial properties arising when the centers follow a prescribed convex pattern: each disk uses a distinct side of a convex polygon as its diameter, and its center is the midpoint of that side. Under the convex position assumption on the disks, it has also been reported that a maximum clique in the corresponding disk graph can be computed in polynomial time [8].

The convex position assumption has also been explored for classical problems that are already polynomial-time solvable in general, as it can simplify the structure and lead to faster algorithms. A well-known example is the linear-time algorithm for computing the Voronoi diagram of points in convex position [4]. Additional results for points in convex position can be found in [21, 27, 10, 32, 18].

A closely related problem is dispersion (also known as the maximally separated set problem [2]). Given a set of points in the plane and an integer $k$, the goal is to select $k$ points that maximize their minimum pairwise distance; the problem is NP-hard in general [34]. When the points are in convex position, however, the problem becomes polynomial-time solvable [30, 33], and the previously best algorithm runs in $O(n^{37/11}\log n)$ time [33]. Our dispersion problem generalizes this setting from points to disks and our algorithm is even faster.

For three disk indices $i,j,k$, we call an ordered triple $(i,j,k)$ a canonical triple if $D_i$, $D_j$, and $D_k$ appear on $\partial \mathscr{H}(𝒟)$ in counterclockwise order and $\{D_i,D_j,D_k\}$ is a strongly convex independent set.

For a canonical triple $(i,j,k)$, since $\{D_i,D_j,D_k\}$ is a strongly convex independent set, the disk $D_{ijk}$ exists by Lemma 1. We define ${𝒟}_k(i,j)$ as the set of disks $D\in 𝒟(i,j)$ such that $D$ is disjoint from $D_i$, $D_j$, and $D_{ijk}$. For convenience, for any two disk indices $i$ and $j$ such that $D_i$ is disjoint from $D_j$, we also treat $(i,j,0)$ as a canonical triple, and define ${𝒟}_0(i,j)$ to be the set of disks $D\in 𝒟(i,j)$ that are disjoint from both $D_i$ and $D_j$.

For a canonical triple $(i,j,k)$, including the case $k=0$, let ${𝒟}_k^{\prime }(i,j)$ denote the subset of disks $D\in {𝒟}_k(i,j)$ such that $\{D,D_i,D_j\}$ is strongly convex.

We now prove Lemma 3. Consider a canonical triple $(i,j,k)$. Without loss of generality, we assume that the centers $p_i$ and $p_j$ of disks $D_i$ and $D_j$ lie on the same horizontal line, with $p_i$ to the left of $p_j$. This assumption allows us to clearly distinguish the upper and lower (outer) common tangents of $D_i$ and $D_j$.

If $k\ne 0$, then by definition $\{D_i,D_j,D_k\}$ is a strongly convex independent set, and the disk $D_{ijk}$ exists by Lemma 1. In the special case $k=0$, we let $D_{ijk}$ denote the upper halfplane bounded by the upper common tangent line of $D_i$ and $D_j$. Accordingly, its center $v_{ijk}$ is interpreted as a point with infinitely large $y$-coordinate and its radius $r_{ijk}$ is taken to be infinite. With this convention, the arguments below apply uniformly to both cases $k=0$ and $k\ne 0$.

If ${𝒟}_k^{\prime }(i,j)=\mathrm{\varnothing }$, then $f(i,j,k)=0$ by Corollary 6, which is proved using Lemma 5.

We now discuss how to implement the algorithm. We focus on computing $W^{\ast }$. By slightly modifying the algorithm using a standard backtracking technique, an actual maximum-weight independent set can also be recovered within asymptotically the same time complexity.

To compute $W^{\ast }$, Lemma 4 implies that it suffices to compute $f(i,j,k)$ for all canonical triples $(i,j,k)$, including the case $k=0$. To this end, by Equation (1), we must determine an order for solving the subproblems such that, when computing a value $f(i,j,k)$, all values $f(i,l,j)$ and $f(l,j,i)$ for $D_l\in {𝒟}_k^{\prime }(i,j)$ have already been computed.

We process pairs $(i,j)$ in increasing order of $j$, and for each fixed $j$ in decreasing order of $i$: for $j=2,\mathrm{\dots },n$, we consider $i=j-1,j-2,\mathrm{\dots },1$ in this order. If $D_i\cap D_j\ne \mathrm{\varnothing }$, we simply set $f(i,j,0)=-W_i-W_j$. Otherwise, we compute $f(i,j,0)$ using Equation (1). Next, for each disk $D_k\in 𝒟(j,i)$ such that $(i,j,k)$ is canonical, we compute $f(i,j,k)$ using Equation (1). With this ordering, every $f$-value appearing on the right-hand side of Equation (1) involves indices that lie between $i$ and $j$ in cyclic order, and hence has already been computed.

Using Equation (1), each subproblem $f(i,j,k)$ can be computed in $O(n)$ time by scanning all disks $D_l\in {𝒟}_k^{\prime }(i,j)$. Since there are $O(n^3)$ subproblems, the total running time of the algorithm is $O(n^4)$.

For each disk $D_i\in 𝒟$, $D_i$ contributes a single arc ${\alpha }_i$ to the boundary $\partial \mathscr{H}(𝒟)$. Let $a_i$ denote the midpoint of ${\alpha }_i$, and let ${\mathrm{\ell }}_i$ be the line through $a_i$ that is tangent to $D_i$. Thus, ${\mathrm{\ell }}_i$ is also tangent to $\mathscr{H}(𝒟)$ at $a_i$. We orient ${\mathrm{\ell }}_i$ so that $D_i$ lies to the left of ${\mathrm{\ell }}_i$ (see Figure 7).

For each pair of consecutive disks $D_i$ and $D_{i+1}$ along $\partial \mathscr{H}(𝒟)$ (if $i=n$, then we let $i+1$ take modulo $n$, which equals $1$), we proceed as follows. Let ${\rho }_{i,i+1}$ be the directed common tangent line of $D_i$ and $D_{i+1}$ such that both disks lie to the left of ${\rho }_{i,i+1}$. By the definition of the disk order along $\partial \mathscr{H}(𝒟)$, the convex hull $\mathscr{H}(𝒟)$ lies entirely to the left of ${\rho }_{i,i+1}$, and the segment of ${\rho }_{i,i+1}$ between the two tangency points on $D_i$ and $D_{i+1}$ forms an edge of $\mathscr{H}(𝒟)$.

Since ${\mathrm{\ell }}_i$ is tangent to $D_i$ at the midpoint of ${\alpha }_i$, the line ${\mathrm{\ell }}_i$ must intersect ${\rho }_{i,i+1}$. Similarly, ${\mathrm{\ell }}_{i+1}$ intersects ${\rho }_{i,i+1}$. Moreover, because $n\ge 3$, the lines ${\mathrm{\ell }}_i$ and ${\mathrm{\ell }}_{i+1}$ intersect at a point $b_i$ that lies to the right of ${\rho }_{i,i+1}$ (see Figure 7).

We define $B$ as the set of all such intersection points $b_i$, for $1\le i\le n$. Thus, $|B|=n$.

If we treat each point $b_i$ as a special disk, then this construction places $b_{i-1}$, $D_i$, and $b_i$ in a degenerate configuration, since ${\mathrm{\ell }}_i$ is tangent to all three. Note that our algorithm in Section 3 also works for such degenerate cases. Alternatively, if desired, one could perturb each point $b_i$ infinitesimally toward ${\rho }_{i,i+1}$ so that the set $S=𝒟\cup B$ is in general position. In what follows, we retain the definition of $B$ above and allow degeneracies, as this simplifies the exposition.

Since the convex hull $\mathscr{H}(𝒟)$ can be computed in $O(n\log n)$ time [26], the set $B$ can also be constructed in $O(n\log n)$ time.

The following lemma proves that $B$ has the two desired properties.