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:
| S | ≥ | M D S ( C ) | M {\displaystyle |S|\geq {\frac {|MDS(C)|}{M}}}
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):
… excerpt ends here. Continue reading the full article.
