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 xi in C: Calculate J(xi), the subset of all shapes in C that intersect xi (including xi itself). Assign N(xi) equal to the number shapes in J(xi). Choose any xj such that N(xj) is a maximum, i.e. a shape that touches as many shapes as any other. Of all of the shapes xi that intersect xj (including xj itself), select the shape x that touches the fewest other shapes, i.e. x such that. N(x) is a minimum Add x to S. Remove x from C, and delete J(x) and N(x) 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.
The main challenge with this approach is to find a geometric way to divide the set into subsets. This may require to discard a small number of shapes that do not fit into any one of the subsets, as explained in the following subsections.
Axis-parallel rectangles with the same height: 2-approximation Let C be a set of n axis-parallel rectangles in the plane, all with the same height H but with varying lengths. The following algorithm finds a disjoint set with a size of at least |MDS(C)|/2 in time O(n log n):
Draw m horizontal lines, such that: The separation between two lines is strictly more than H. Each line intersects at least one rectangle (hence m ≤ n). Each rectangle is intersected by exactly one line. Since the height of all rectangles is H, it is not possible that a rectangle is intersected by more than one line. Therefore, the lines partition the set of rectangles into m subsets () – each subset includes the rectangles intersected by a single line. For each subset , compute an exact MDS using the one-dimensional greedy algorithm (see above). By construction, the rectangles in () can intersect only rectangles in or in . Therefore, each of the following two unions is a disjoint sets: Union of odd MDSs: Union of even MDSs: Return the largest of these two unions. Its size must be at least |MDS|/2.
Axis-parallel rectangles with the same height: PTAS Let C be a set of n axis-parallel rectangles in the plane, all with the same height but with varying lengths. There is an algorithm that finds a disjoint set with a size of at least |MDS(C)|/(1 + 1/k) in time O(n2k−1), for every constant k > 1.
The algorithm is an improvement of the above-mentioned 2-approximation, by combining dynamic programming with the shifting technique of Hochbaum and Maass.
This algorithm can be generalized to d dimensions. If the labels have the same size in all dimensions except one, it is possible to find a similar approximation by applying dynamic programming along one of the dimensions. This also reduces the time to n^O(1/e).
Axis-parallel rectangles: Logarithmic-factor approximation Let C be a set of n axis-parallel rectangles in the plane. The following algorithm finds a disjoint set with a size of at least in time :
INITIALIZATION: sort the horizontal edges of the given rectangles by their y-coordinate, and the vertical edges by their x-coordinate (this step takes time O(n log n)). STOP CONDITION: If there are at most n ≤ 2 shapes, compute the MDS directly and return. RECURSIVE PART: Let be the median x-coordinate. Partition the input rectangles into three groups according to their relation to the line : those entirely to its left (), those entirely to its right (), and those intersected by it (). By construction, the cardinalities of and are at most n/2. Recursively compute an approximate MDS in () and in (), and calculate their union. By construction, the rectangles in and are all disjoint, so is a disjoint set. Compute an exact MDS in (). Since all rectangles in intersect a single vertical line , this computation is equivalent to finding an MDS from a set of intervals, and can be solved exactly in time O(n log n) (see above). Return either or – whichever of them is larger.
It is provable by induction that, at the last step, either or have a cardinality of at least .
Chalermsookk and Chuzoy have improved the factor to .
Chalermsook and Walczak have presented an -approximation algorithm to the more general setting, in which each rectangle has a weight, and the goal is to find an independent set of maximum total weight.
Axis-parallel rectangles: constant-factor approximation For a long time, it was not known whether a constant-factor approximation exists for axis-parallel rectangles of different lengths and heights. It was conjectured that such an approximation could be found using guillotine cuts. Particularly, if there exists a guillotine separation of axes-parallel rectangles in which rectangles are separated, then it can be used in a dynamic programming approach to find a constant-factor approximation to the MDS.
To date, it is not known whether such a guillotine separation exists. However, there are constant-factor approximation algorithms using non-guillotine cuts:
Joseph S. B. Mitchell presented a 10-factor approximation algorithm. His algorithm is based on partitioning the plane into corner-clipped rectangles. Gálvez, Khan, Mari, Mömke, Pittu, and Wiese presented an algorithm partitioning the plane into a more general class of polygons. This simplifies the analysis and improves the approximation to 6-factor. Additionally, they improved the approximation to 3-factor and then to (2+ε)-factor.
Fat objects with identical sizes: PTAS Let C be a set of n squares or circles of identical size. Hochbaum and Maass presented a polynomial-time approximation scheme for finding an MDS using a simple shifted-grid strategy. It finds a solution within (1 − ε) of the maximum in time nO(1/ε2) time and linear space. The strategy generalizes to any collection of fat objects of roughly the same size (i.e., when the maximum-to-minimum size ratio is bounded by a constant).
Fat objects with arbitrary sizes: PTAS Let C be a set of n fat objects, such as squares or circles, of arbitrary sizes. There is a PTAS for finding an MDS based on multi-level grid alignment. It has been discovered by two groups in approximately the same time, and described in two different ways.
Level partitioning An algorithm of Erlebach, Jansen and Seidel finds a disjoint set with a size of at least (1 − 1/k)2 ⋅ |MDS(C)| in time nO(k2), for every constant k > 1. It works in the following way.
Scale the disks so that the smallest disk has diameter 1. Partition the disks to levels, based on the logarithm of their size. I.e., the j-th level contains all disks with diameter between (k + 1)j and (k + 1)j+1, for j ≤ 0 (the smallest disk is in level 0).
For each level j, impose a grid on the plane that consists of lines that are (k + 1)j+1 apart from each other. By construction, every disk can intersect at most one horizontal line and one vertical line from its level.
For every r, s between 0 and k, define D(r,s) as the subset of disks that are not intersected by any horizontal line whose index modulo k is r, nor by any vertical line whose index modulu k is s. By the pigeonhole principle, there is at least one pair (r,s) such that , i.e., we can find the MDS only in D(r,s) and miss only a small fraction of the disks in the optimal solution:
For all k2 possible values of r,s (0 ≤ r,s < k), calculate D(r,s) using dynamic programming. Return the largest of these k2 sets.
Shifted quadtrees
An algorithm of Chan finds a disjoint set with a size of at least (1 − 2/k)⋅|MDS(C)| in time nO(k), for every constant k > 1.
The algorithm uses shifted quadtrees. The key concept of the algorithm is alignment to the quadtree grid. An object of size r is called k-aligned (where k ≥ 1 is a constant) if it is inside a quadtree cell of size at most kr (R ≤ kr).