Maximum disjoint set
In computational geometry, a maximum disjoint set is a largest set of non-overlapping geometric shapes selected from a given set of candidate shapes.
Finding an MDS is important in applications such as automatic label placement, VLSI circuit design, and cellular frequency division multiplexing.
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 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 for finding a MDS.
In the following text, MDS denotes the maximum disjoint set in a set C.
Greedy algorithms
Given a set C of shapes, an approximation to MDS can be found by the following greedy algorithm:- INITIALIZATION: Initialize an empty set, S.
- SEARCH: For every shape x in C:
- # Calculate N - the subset of all shapes in C that intersect x.
- # Calculate the largest independent set in this subset: MDS.
- # Select an x such that |MDS| is minimized.
- Add x to S.
- Remove x and N from C.
- If there are shapes in C, go back to Search.
- END: return the set S.
In particular, if we can guarantee that there is an x for which |MDS| is bounded by a constant, 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 intersect each other, and MDS has a size of at most 1.Therefore, in the 1-dimensional case, the MDS can be found exactly in time O:
- Sort the intervals in ascending order of their bottom endpoints.
- Add an interval with the highest bottom endpoint, and delete all intervals intersecting it.
- Continue until no intervals remain.
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 intersects at most 3 other disjoint disks. Therefore the greedy algorithm yields a 3-approximation, i.e., it finds a disjoint set with a size of at least MDS/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.
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.
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.
- 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.
- Return either or – whichever of them is larger.
The approximation factor has been reduced to and generalized to the case in which rectangles have different weights.
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|/2 in time O:- Draw m horizontal lines, such that:
- # The separation between two lines is strictly more than H.
- # Each line intersects at least one rectangle.
- # 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.
- 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
The algorithm is an improvement of the above-mentioned 2-approximation, by combining dynamic programming with the shifting technique of.
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.
Fat objects with identical sizes: PTAS
Let C be a set of n squares or circles of identical size. There is a polynomial-time approximation scheme for finding an MDS using a simple shifted-grid strategy. It finds a solution within of the maximum in time nO time and linear space. The strategy generalizes to any collection of fat objects of roughly the same size.Fat objects with arbitrary sizes: PTAS
Let C be a set of n fat objects 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.Version 1 finds a disjoint set with a size of at least 2 · |MDS| in time nO, for every constant k > 1:
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 j and j+1, for j ≤ 0.
For each level j, impose a grid on the plane that consists of lines that are 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 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 ' such that, i.e., we can find the MDS only in D and miss only a small fraction of the disks in the optimal solution:
- For all k2 possible values of r,s, calculate D using dynamic programming.
- Return the largest of these k2 sets.
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 if it is inside a quadtree cell of size at most kr.
By definition, a k-aligned object that intersects the boundary of a quatree cell of size R must have a size of at least R/k. The boundary of a cell of size R can be covered by 4k squares of size R/k; hence the number of disjoint fat objects intersecting the boundary of that cell is at most 4kc, where c is a constant measuring the fatness of the objects.
Therefore, if all objects are fat and k-aligned, it is possible to find the exact maximum disjoint set in time nO using a divide-and-conquer algorithm. Start with a quadtree cell that contains all objects. Then recursively divide it to smaller quadtree cells, find the maximum in each smaller cell, and combine the results to get the maximum in the larger cell. Since the number of disjoint fat objects intersecting the boundary of every quadtree cell is bounded by 4kc, we can simply "guess" which objects intersect the boundary in the optimal solution, and then apply divide-and-conquer to the objects inside.
If almost all objects are k-aligned, we can just discard the objects that are not k-aligned, and find a maximum disjoint set of the remaining objects in time nO. This results in a approximation, where e is the fraction of objects that are not k-aligned.
If most objects are not k-aligned, we can try to make them k-aligned by shifting the grid in multiples of. First, scale the objects such that they are all contained in the unit square. Then, consider k shifts of the grid:,,,..., /k,. I.e., for each j in, consider a shift of the grid in. It is possible to prove that every label will be 2k-aligned for at least k − 2 values of j. Now, for every j, discard the objects that are not k-aligned in the shift, and find a maximum disjoint set of the remaining objects. Call that set A. Call the real maximum disjoint set is A*. Then:
Therefore, the largest A has a size of at least: |A*|. The return value of the algorithm is the largest A; the approximation factor is, and the run time is nO. We can make the approximation factor as small as we want, so this is a PTAS.
Both versions can be generalized to d'' dimensions and to the weighted case.
Geometric separator algorithms
Several divide-and-conquer algorithms are based on a certain geometric separator theorem. A geometric separator is a line or shape that separates a given set of shapes to two smaller subsets, such that the number of shapes lost during the division is relatively small. This allows both PTASs and sub-exponential exact algorithms, as explained below.Fat objects with arbitrary sizes: PTAS using geometric separators
Let C be a set of n fat objects of arbitrary sizes. The following algorithm finds a disjoint set with a size of at least )·|MDS| in time nO, for every constant b > 1.The algorithm is based on the following geometric separator theorem, which can be proved similarly to the proof of the existence of geometric separator for disjoint squares:
where a and c are constants. If we could calculate MDS exactly, we could make the constant a as low as 2/3 by a proper selection of the separator rectangle. But since we can only approximate MDS by a constant factor, the constant a must be larger. Fortunately, a remains a constant independent of |C|.
This separator theorem allows to build the following PTAS:
Select a constant b. Check all possible combinations of up to b + 1 labels.
- If |MDS| has a size of at most b then just return that MDS and exit. This step takes nO time.
- Otherwise, use a geometric separator to separate C to two subsets. Find the approximate MDS in Cinside and Coutside separately, and return their combination as the approximate MDS in C.
The solution to this recurrence is:
i.e.,. We can make the approximation factor as small as we want by a proper selection of b.
This PTAS is more space-efficient than the PTAS based on quadtrees, and can handle a generalization where the objects may slide, but it cannot handle the weighted case.
Disks with a bounded size-ratio: exact sub-exponential algorithm
Let C be a set of n disks, such that the ratio between the largest radius and the smallest radius is at most r. The following algorithm finds MDS exactly in time.The algorithm is based on a width-bounded geometric separator on the set Q of the centers of all disks in C. This separator theorem allows to build the following exact algorithm:
- Find a separator line such that at most 2n/3 centers are to its right, at most 2n/3 centers are to its left, and at most O centers are at a distance of less than r/2 from the line.
- Consider all possible non-overlapping subsets of Cint. There are at most such subsets. For each such subset, recursively compute the MDS of Cleft and the MDS of Cright, and return the largest combined set.
The solution to this recurrence is:
Local search algorithms
Pseudo-disks: a PTAS
A pseudo-disks-set is a set of objects in which the boundaries of every pair of objects intersect at most twice.. A pseudo-disks-set has a bounded union complexity, i.e., the number of intersection points on the boundary of the union of all objects is linear in the number of objects.Let C be a pseudo-disks-set with n objects. The following local search algorithm finds a disjoint set of size at least in time, for every integer constant :
- INITIALIZATION: Initialize an empty set,.
- SEARCH: Loop over all the subsets of whose size is between 1 and. For each such subset X:
- * Verify that X itself is independent ;
- * Calculate the set Y of objects in S that intersect X.
- * If, then remove Y from S and insert X:.
- END: return the set S.
The algorithm is very simple; the difficult part is to prove the approximation ratio.
See also.
Linear programming relaxation algorithms
Pseudo-disks: a PTAS
Let C be a pseudo-disks-set with n objects and union complexity u. Using linear programming relaxation, it is possible to find a disjoint set of size at least. This is possible either with a randomized algorithm that has a high probability of success and run time, or a deterministic algorithm with a slower run time. This algorithm can be generalized to the weighted case.Other classes of shapes for which approximations are known
- Line segments in the two-dimensional plane.
- Arbitrary two-dimensional convex objects.
- Curves with a bounded number of intersection points.