In computational geometry, a maximum disjoint set (MDS) is a largest set of non-overlapping geometric shapes selected from a given set of candidate shapes.
Every set of non-overlapping shapes is an independent set in the intersection graph of the shapes. Therefore, the MDS problem is a special case of the maximum independent set (MIS) problem. Both problems are NP complete, but finding a MDS may be easier than finding a MIS in two respects: For the general MIS problem, the best known exact algorithms are exponential. In some geometric intersection graphs, there are sub-exponential algorithms for finding a MDS. The general MIS problem is hard to approximate and doesn't even have a constant-factor approximation. In some geometric intersection graphs, there are polynomial-time approximation schemes (PTAS) for finding a MDS.
Finding an MDS is important in applications such as automatic label placement, VLSI circuit design, and cellular frequency division multiplexing.
The MDS problem can be generalized by assigning a different weight to each shape and searching for a disjoint set with a maximum total weight.
In the following text, MDS(C) denotes the maximum disjoint set in a set C.
Greedy algorithms
Given a set C of shapes, an approximation to MDS(C) can be found by the following greedy algorithm:
INITIALIZATION: Initialize an empty set, S. SEARCH: For every shape x in C: Calculate N(x) - the subset of all shapes in C that intersect x (including x itself). Calculate the largest independent set in this subset: MDS(N(x)). Select an x such that |MDS(N(x))| is minimized. Add x to S. Remove x and N(x) from C. If there are shapes in C, go back to Search. END: return the set S.
For every shape x that we add to S, we lose the shapes in N(x), because they are intersected by x and thus cannot be added to S later on. However, some of these shapes themselves intersect each other, and thus in any case it is not possible that they all be in the optimal solution MDS(S). The largest subset of shapes that can all be in the optimal solution is MDS(N(x)). Therefore, selecting an x that minimizes |MDS(N(x))| minimizes the loss from adding x to S.
In particular, if we can guarantee that there is an x for which |MDS(N(x))| is bounded by a constant (say, M), then this greedy algorithm yields a constant M-factor approximation, as we can guarantee that:
Such an upper bound M exists for several interesting cases:
1-dimensional intervals: exact polynomial algorithm
When C is a set of intervals on a line, M=1, and thus the greedy algorithm finds the exact MDS. To see this, assume w.l.o.g. that the intervals are vertical, and let x be the interval with the highest bottom endpoint. All other intervals intersected by x must cross its bottom endpoint. Therefore, all intervals in N(x) intersect each other, and MDS(N(x)) has a size of at most 1 (see figure).
Therefore, in the 1-dimensional case, the MDS can be found exactly in time O(n log n): Sort the intervals in ascending order of their bottom endpoints (this takes time O(n log n)). Add an interval with the highest bottom endpoint, and delete all intervals intersecting it. Continue until no intervals remain.
This algorithm is analogous to the earliest deadline first scheduling solution to the interval scheduling problem.
In contrast to the 1-dimensional case, in 2 or more dimensions the MDS problem becomes NP-complete, and thus has either exact super-polynomial algorithms or approximate polynomial algorithms.
Fat shapes: constant-factor approximations
When C is a set of unit disks, M=3, because the leftmost disk (the disk whose center has the smallest x coordinate) intersects at most 3 other disjoint disks (see figure). Therefore the greedy algorithm yields a 3-approximation, i.e., it finds a disjoint set with a size of at least MDS(C)/3.
Similarly, when C is a set of axis-parallel unit squares, M=2.
When C is a set of arbitrary-size disks, M=5, because the disk with the smallest radius intersects at most 5 other disjoint disks (see figure).
Similarly, when C is a set of arbitrary-size axis-parallel squares, M=4.
Other constants can be calculated for other regular polygons.
Divide-and-conquer algorithms
The most common approach to finding a MDS is divide-and-conquer. A typical algorithm in this approach looks like the following:
Divide the given set of shapes into two or more subsets, such that the shapes in each subset cannot overlap the shapes in other subsets because of geometric considerations. Recursively find the MDS in each subset separately. Return the union of the MDSs from all subsets.