Conjunto disjunto máximo

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.
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:
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.
Dado un conjunto C de formas, se puede encontrar una aproximación a CDM(C) mediante el siguiente algoritmo voraz:
Por cada forma x que se agrega a S, se eliminan estas formas en N(x), porque están intersecadas por x y, por lo tanto, no se pueden sumar a S más adelante. Sin embargo, algunas de estas formas se cruzan entre sí y, por lo tanto, en cualquier caso no es posible que todas estén en la solución óptima CDM(S). El subconjunto más grande de formas que "pueden" estar en la solución óptima es "CDM(N(x))". Por lo tanto, seleccionar una x que minimice |CDM(N(x))| minimiza la pérdida al agregar x a S.
En particular, si se puede garantizar que existe una x para la que |CDM(N(x))| está limitada por una constante (póngase por caso, M), entonces este algoritmo voraz produce una aproximación constante del factor M, ya que se puede garantizar que:
Tal límite superior M existe para varios casos interesantes:
Cuando C es un conjunto de intervalos en una recta, M = 1 y, por lo tanto, el algoritmo voraz encuentra el CDM exacto. Para ver esto, supóngase sin pérdida de generalidad que los intervalos son verticales, y sea x el intervalo con el punto final inferior más alto. Todos los demás intervalos intersecados por x deben cruzar su punto final inferior. Por lo tanto, todos los intervalos en N(x) se cruzan entre sí y CDM(N(x)) tiene un tamaño de como máximo 1 (véase la figura).
Por lo tanto, en el caso unidimensional, el CDM se puede encontrar exactamente en el tiempo O(n log n):​
Este algoritmo es análogo al de la solución de la fecha límite más temprana en primera programación en el problema de programación de intervalos.
En contraste con el caso unidimensional, en 2 o más dimensiones el problema de hallar el CDM se vuelve NP-completo y, por lo tanto, tiene algoritmos superpolinomiales exactos o algoritmos polinomiales aproximados.
Cuando C es un conjunto de discos unitarios, M=3,​ porque el disco más a la izquierda (el disco cuyo centro tiene la coordenada x más pequeña) interseca como máximo otros 3 discos disjuntos (véase la imagen). Por lo tanto, el algoritmo voraz produce una aproximación 3, es decir, encuentra un conjunto disjunto con un tamaño de al menos CDM(C)/3.
De manera similar, cuando C es un conjunto de cuadrados unitarios paralelos a los ejes, M=2.
Cuando C es un conjunto de discos de tamaño arbitrario, M=5, porque el disco con el radio más pequeño interseca como máximo a otros 5 discos disjuntos (véase la figura).
De manera similar, cuando C es un conjunto de cuadrados paralelos a los ejes de tamaño arbitrario, M = 4.
Se pueden calcular otras constantes para otros polígonos regulares.​
El enfoque más común para encontrar un CDM es el de divide y vencerás. Un algoritmo típico de este enfoque se parece al siguiente:
El principal desafío de este enfoque es encontrar una forma geométrica de dividir el conjunto en subconjuntos. Esto puede requerir descartar una pequeña cantidad de formas que no encajan en ninguno de los subconjuntos, como se explica en las siguientes subsecciones.
Sea C un conjunto de n rectángulos paralelos a los ejes en el plano, todos con la misma altura H pero con longitudes variables. El siguiente algoritmo encuentra un conjunto disjunto con un tamaño de al menos |CDM(C)|/2 en el tiempo O(n log n):​
Sea C un conjunto de n rectángulos paralelos a los ejes en el plano, todos con la misma altura pero con longitudes variables. Existe un algoritmo que encuentra un conjunto disjunto con un tamaño de al menos |CDM(C)|/(1 + 1/k) en el tiempo O( n), para cada constante k > 1.​
El algoritmo es una mejora de la aproximación 2 mencionada anteriormente, combinando programación dinámica con la técnica de desplazamiento de Hochbaum y Maass.​
Este algoritmo se puede generalizar a d dimensiones. Si las etiquetas tienen el mismo tamaño en todas las dimensiones excepto una, es posible encontrar una aproximación similar aplicando programación dinámica en una de las dimensiones. Esto también reduce el tiempo a n^O(1/e).​
Sea C un conjunto de n rectángulos paralelos a los ejes en el plano. El siguiente algoritmo encuentra un conjunto disjunto con un tamaño de al menos | C D M ( C ) | log ⁡ n {\displaystyle {\frac {|CDM(C)|}{\log {n}}}} en el tiempo O ( n log ⁡ n ) {\displaystyle O(n\log {n})} :​
Se puede demostrar por inducción que, en el último paso, M l e f t ∪ M r i g h t {\displaystyle M_{\mathrm {left} }\cup M_{\mathrm {right} }} o M i n t {\displaystyle M_{\mathrm {int} }} tienen una cardinalidad de al menos | C D M ( C ) | log ⁡ n {\displaystyle {\frac {|CDM(C)|}{\log {n}}}} .
Chalermsookk y Chuzoy​ mejoraron el factor a O ( log ⁡ log ⁡ n ) {\displaystyle O(\log {\log {n}})} .
Chalermsookk y Walczak​ presentaron un algoritmo de aproximación O ( log ⁡ log ⁡ n ) {\displaystyle O(\log {\log {n}})} a un entorno más general, en el que cada rectángulo tiene un "peso", y el objetivo es encontrar un conjunto independiente de peso total máximo.
Durante mucho tiempo no se supo si existe una aproximación de factor constante para rectángulos paralelos a sus ejes de diferentes longitudes y alturas. Se conjeturó que tal aproximación podría encontrarse utilizando "cortes de guillotina". En particular, si existe un corte con guillotina de rectángulos paralelos a los ejes en los que los rectángulos Ω ( n ) {\displaystyle \Omega (n)} están separados, entonces se puede utilizar en un enfoque de programación dinámica para encontrar una aproximación de factor constante al CDM.​
Hasta la fecha, no se sabe si existe tal separación mediante cortes con guillotina. Sin embargo, existen algoritmos de aproximación de factor constante que utilizan cortes pero sin guillotina:
Sea C un conjunto de n cuadrados o círculos de tamaño idéntico. Hochbaum y Maass​ presentaron un esquema de aproximación de tiempo polinómico para encontrar un CDM utilizando una estrategia simple de cuadrícula desplazada. El procedimiento encuentra una solución dentro de (1 − ε) del máximo en el tiempo n, de tiempo y espacio lineal. La estrategia se generaliza a cualquier colección de objeto grueso de aproximadamente el mismo tamaño (es decir, cuando la relación de tamaño máximo a mínimo está limitada por una constante).
Sea C un conjunto de n objetos gruesos, como cuadrados o círculos, de tamaños arbitrarios. Existe un EATP para encontrar un CDM basado en la alineación de la cuadrícula en varios niveles. Ha sido descubierto por dos grupos aproximadamente al mismo tiempo y descrito de dos maneras diferentes.
Un algoritmo de Erlebach, Jansen y Seidel​ encuentra un conjunto disjunto con un tamaño de al menos (1 − 1/k) · |CDM(C)| en el tiempo n, para cada constante k > 1. Funciona de la siguiente manera:
Un algoritmo de Chan​ encuentra un conjunto disjunto con un tamaño de al menos (1 − 2/k)·|CDM(C)| en el tiempo n, para cada constante k > 1.
El algoritmo utiliza árboles cuadrados desplazados. El concepto clave del algoritmo es el de la "alineación" con la cuadrícula del árbol cuádruple. Un objeto de tamaño r se llama k-alineado (donde k ≥ 1 es una constante) si está dentro de una celda de árbol cuádruple de tamaño como máximo kr(R ≤ kr).
Por definición, un objeto alineado con k que interseca el límite de una celda de cuatro árboles de tamaño R debe tener un tamaño de al menos R/k (r > R/k). El límite de una celda de tamaño R puede estar cubierto por 4k cuadrados de tamaño R/k. Por lo tanto, el número de objetos grasos disjuntos que cruzan el límite de esa celda es como máximo 4kc, donde c es una constante que mide el grosor de los objetos.
Por lo tanto, si todos los objetos son gruesos y están alineados con k, es posible encontrar el conjunto disjunto máximo exacto en el tiempo n usando un algoritmo de divide y vencerás. Comienza con una celda del árbol cuádruple que contenga todos los objetos. Luego, se divide de forma recursiva en celdas del árbol cuádruple más pequeñas, se encuentra el máximo en cada celda más pequeña y se combinan los resultados para obtener el máximo en la celda más grande. Dado que el número de objetos gruesos disjuntos que intersecan el límite de cada celda del árbol cuádruple está limitado por 4kc, se puede simplemente "adivinar" qué objetos intersecan el límite en la solución óptima y luego aplicar divide y vencerás a los objetos en su interior.
Si casi todos los objetos están alineados con k, se puede simplemente descartar los objetos que no están alineados con k y encontrar un conjunto máximo disjunto de los objetos restantes en el tiempo n. Esto da como resultado una aproximación (1 − e), donde e es la fracción de objetos que no están alineados con k.
Si la mayoría de los objetos no están alineados con k, se puede intentar alinearlos con k''desplazando la cuadrícula en múltiplos de (1/k,1/ k). Primero, escalar los objetos de modo que todos estén contenidos en el cuadrado unitario. Luego, considerar los k desplazamientos de la cuadrícula: (0,0), (1/k,1/k), (2/k,2/ k), ..., ((k − 1)/k,(k − 1)/k' '). Es decir, para cada j en {0,...,k − 1}, considerar un desplazamiento de la cuadrícula en (j/k,j/k). Es posible demostrar que cada etiqueta estará alineada con 2k para al menos k −2 valores de j. Ahora, para cada j, descartar los objetos que no estén alineados con k en los saltos de (j/k,j/k) y encontrar el conjunto primario disjunto máximo de los objetos restantes. Llamar a ese conjunto A(j), y llamar al conjunto disjunto máximo real es A*. Entonces:
Por lo tanto, el A(j) más grande tiene un tamaño de al menos: (1 − 2/k)|A*|. El valor de retorno del algoritmo es el mayor A(j). El factor de aproximación es (1 − 2/k) y el tiempo de ejecución es n. Se puede hacer que el factor de aproximación sea tan pequeño como se quiera, por lo que este es un EATP.
Ambas versiones se pueden generalizar a d dimensiones (con diferentes relaciones de aproximación) y al caso ponderado.
Varios algoritmos de divide y vencerás se basan en el teorema del separador geométrico. Un separador geométrico es una línea o forma que separa un conjunto determinado de formas en dos subconjuntos más pequeños, de modo que el número de formas perdidas durante la división es relativamente pequeño. Esto permite tanto trabajar con procedimientos EATP y con algoritmos exactos subexponenciales, tal como se explica a continuación.
Sea C un conjunto de nobjetos gruesos, como cuadrados o círculos, de tamaños arbitrarios. Chan​ describió un algoritmo que encuentra un conjunto disjunto con un tamaño de al menos (1 − O(√b))·|CDM(C)| en el tiempo n, para cada constante b > 1.
El algoritmo se basa en el siguiente teorema del separador geométrico, que se puede demostrar de manera similar a la prueba de la existencia de un separador geométrico para cuadrados disjuntos:
donde a y c son constantes. Si se pudiera calcular CDM(C) exactamente, sería posible hacer que la constante a sea tan baja como 2/3 mediante una selección adecuada del rectángulo separador. Pero como solo se puede aproximar el CDM(C) mediante un factor constante, la constante a debe ser mayor. Afortunadamente, a sigue siendo una constante independiente de |C|.
Este teorema del separador permite construir los siguientes EATP:
Seleccionar una constante b. Consultar todas las combinaciones posibles de hasta b + 1 etiquetas.
Sea E(m) el error del algoritmo anterior cuando el tamaño óptimo del CDM es CDM(C) = m. Cuando m ≤ b, el error es 0 porque el conjunto disjunto máximo se calcula exactamente; cuando m > b, el error aumenta como máximo c√m el número de etiquetas intersecadas por el separador. El peor caso para el algoritmo es cuando la división en cada paso está en la proporción máxima posible, que es a:(1 − a). Por tanto, la función de error satisface la siguiente relación de recurrencia:
La solución a esta recurrencia es:
es decir, E ( m ) = O ( m / b ) {\displaystyle E(m)=O(m/{\sqrt {b}})} . Se puede hacer que el factor de aproximación sea tan pequeño como se quiera mediante una selección adecuada de b.
Este EATP ahorra más espacio que el EATP basado en árboles cuádruples y puede manejar una generalización en la que los objetos pueden deslizarse, pero no puede manejar el caso ponderado.
Sea C un conjunto de n discos, tal que la relación entre el radio mayor y el radio menor sea como máximo r. El siguiente algoritmo encuentra CDM(C) exactamente en el tiempo 2 O ( r ⋅ n ) {\displaystyle 2^{O(r\cdot {\sqrt {n}})}} .​
El algoritmo se basa en un separador geométrico acotado por ancho en el conjunto Q de los centros de todos los discos en C. Este teorema del separador permite construir el siguiente algoritmo exacto:
El tiempo de ejecución de este algoritmo satisface la siguiente relación de recurrencia:
La solución a esta recurrencia es:
Un conjunto de pseudodiscos es un conjunto de objetos en el que los límites de cada par de objetos se cruzan como máximo dos veces (téngase en cuenta que esta definición se refiere a una colección completa y no dice nada sobre las formas específicas de los objetos de la colección). Un conjunto de pseudodiscos tiene una complejidad de unión acotada, es decir, el número de puntos de intersección en el límite de la unión de todos los objetos es lineal con respecto al número de objetos. Por ejemplo, un conjunto de cuadrados o círculos de tamaños arbitrarios es un conjunto de pseudodiscos.
Sea C un conjunto de pseudodiscos con n objetos. Un algoritmo de búsqueda local de Chan y Har-Peled​ permite encontrar un conjunto disjunto de tamaño al menos ( 1 − O ( 1 b ) ) ⋅ | C D M ( C ) | {\displaystyle (1-O({\frac {1}{\sqrt {b}}}))\cdot |CDM(C)|} en el tiempo O ( n b + 3 ) {\displaystyle O(n^{b+3})} , para cada constante entera b ≥ 0 {\displaystyle b\geq 0} :
Cada intercambio en el paso de búsqueda aumenta el tamaño de S en al menos 1 y, por lo tanto, puede ocurrir como máximo n veces.
El algoritmo es muy simple, y la parte difícil es demostrar la relación de aproximación.​
Véase también al respecto el trabajo de P. K. Agarwal y de N. H. Mustafa.​
Sea C un conjunto de pseudodiscos con n objetos y complejidad de unión u. Usando relajación en programación lineal, es posible encontrar un conjunto disjunto de tamaño al menos n u ⋅ | C D M ( C ) | {\displaystyle {\frac {n}{u}}\cdot |CDM(C)|} . Esto es posible con un algoritmo aleatorio que tiene una alta probabilidad de éxito y un tiempo de ejecución O ( n 3 ) {\displaystyle O(n^{3})} , o un algoritmo determinista con un tiempo de ejecución más lento (pero todavía polinomial). Este algoritmo se puede generalizar al caso ponderado.​