![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/5/51/Maximum_disjoint_set.svg/langes-640px-Maximum_disjoint_set.svg.png&w=640&q=50)
Conjunto disjunto máximo
concepto en geometría computacional / De Wikipedia, la enciclopedia encyclopedia
En geometría computacional, un conjunto disjunto máximo (CDM) es el conjunto más grande de formas geométricas no superpuestas formable a partir de un conjunto dado de formas candidatas.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/5/51/Maximum_disjoint_set.svg/640px-Maximum_disjoint_set.svg.png)
Cada conjunto de formas que no se superponen es un conjunto independiente en el grafo de intersección de las formas. Por lo tanto, el problema del CDM es un caso especial del problema del conjunto independiente máximo (CIM). Ambos problemas son NP-completos, pero encontrar un CDM puede ser más fácil que encontrar un CIM en dos aspectos:
- Para el problema general del CIM, los algoritmos exactos más conocidos son exponenciales. En cambio, para algunos grafos de intersección geométrica, existen algoritmos subexponenciales para encontrar un CDM.[1]
- El problema general de encontrar el CIM es difícil de aproximar y ni siquiera tiene una aproximación de factor constante. Para algunos grafos de intersección geométrica, existen esquemas de aproximación de tiempo polinómico (EATPs) para encontrar un CDM.
Encontrar un CDM es importante en aplicaciones como asignación automática de etiquetas, diseño de circuitos integrados y multiplexación por división de frecuencia celular.
El problema de determinar un CDM se puede generalizar asignando un peso diferente a cada forma y buscando un conjunto disjunto con un peso total máximo.
En el siguiente texto, CDM(C) denota el conjunto disjunto máximo de un conjunto C.