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.[1]
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.
^Ravi, S. S.; Hunt, H. B. (1987). "An application of the planar separator theorem to counting problems". Information Processing Letters. 25 (5): 317. doi:10.1016/0020-0190(87)90206-7., Smith, W. D.; Wormald, N. C. (1998). "Geometric separator theorems and applications". Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280). p. 232. doi:10.1109/sfcs.1998.743449. ISBN 978-0-8186-9172-0. S2CID 17962961.
and 22 Related for: Maximum disjoint set information
geometry, a maximumdisjointset (MDS) is a largest set of non-overlapping geometric shapes selected from a given set of candidate shapes. Every set of non-overlapping...
pairwise disjoint in polynomial time. The optimization version of the problem, maximumset packing, asks for the maximum number of pairwise disjointsets in...
Fuzzy sets are disjoint if and only if their supports are disjoint according to the standard definition for crisp sets. For disjoint fuzzy sets A , B...
packing should be separable using only guillotine cuts. Maximumdisjointset (or Maximum independent set) is a problem in which both the sizes and the locations...
the maximum flow is k {\displaystyle k} iff there are k {\displaystyle k} edge-disjoint paths. 2. The paths must be independent, i.e., vertex-disjoint (except...
{\displaystyle n=2^{(k+1)}-2} elements. The set system consists of k {\displaystyle k} pairwise disjointsets S 1 , … , S k {\displaystyle S_{1},\ldots...
closed under complements and countable disjoint unions π-system – Family of sets closed under intersection Ring of sets – Family closed under unions and relative...
notation was utilized in definitions; for example, Cantor defined two sets as being disjoint if their intersection has an absence of points; however, it is debatable...
occurs if and only if A {\displaystyle A} and B {\displaystyle B} are disjointsets. Furthermore, denoting D = A Δ B {\displaystyle D=A\mathbin {\Delta...
problem is 1-dimensional – only the time dimension is relevant. The Maximumdisjointset problem is a generalization to 2 or more dimensions. This generalization...
algorithms can use any of the algorithms for finding the maximumdisjointset from the set of potential labels. Other algorithms can also be used, like...
vertices. The domatic number is the maximum size of a domatic partition, that is, the maximum number of disjoint dominating sets. The graph in the figure has...
disjoint convex sets in n-dimensional Euclidean space. There are several rather similar versions. In one version of the theorem, if both these sets are...
the vertices into disjoint dominating sets. The domatic number is the maximum size of a domatic partition. An eternal dominating set is a dynamic version...
the feedback arc set problem obeys a min-max theorem: the minimum size of a feedback arc set equals the maximum number of edge-disjoint directed cycles...
four cap sets, the single point that when added to the 20 points of a cap set makes the entire sum go to 0 (mod 3). All cap sets in such a disjoint collection...
into two disjointsets such that the vertices in one set are not connected to each other, but may be connected to vertices in the other set. Put another...
estimation Quadtrees are also used in the area of fractal image analysis Maximumdisjointsets Quadtrees, particularly the region quadtree, have lent themselves...
members of X. Open balls of radius r centered at the points of X will all be disjoint from each other. The covering radius, R, of X is the smallest distance...
then it implies an O(1) approximation algorithm to the problem of maximumdisjointset of axes-parallel rectangles in time O ( n 5 ) {\displaystyle O(n^{5})}...
separating set 1. A separating set is a set containing a given set and disjoint from another given set 2. A separating set is a set S of functions on a set such...
Global Information