En geometría computacional , un conjunto disjunto máximo (MDS) es un conjunto más grande de formas geométricas no superpuestas seleccionadas de un conjunto dado de formas candidatas.
Cada conjunto de formas que no se superponen es un conjunto independiente en el gráfico de intersección de las formas. Por lo tanto, el problema de MDS es un caso especial del problema de conjunto independiente máximo (MIS) . Ambos problemas son NP completos , pero encontrar un MDS puede ser más fácil que encontrar un MIS en dos aspectos:
- Para el problema general de MIS, los algoritmos exactos más conocidos son exponenciales. En algunos gráficos de intersección geométrica, existen algoritmos sub-exponenciales para encontrar un MDS. [1]
- El problema general de MIS es difícil de aproximar y ni siquiera tiene una aproximación de factor constante. En algunos gráficos de intersección geométrica, existen esquemas de aproximación de tiempo polinómico (PTAS) para encontrar un MDS.
Encontrar un MDS es importante en aplicaciones como la colocación automática de etiquetas , el diseño de circuitos VLSI y la multiplexación por división de frecuencia celular .
El problema de MDS 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, MDS ( C ) indica la máxima conjunto disjuntos en un conjunto C .
Algoritmos codiciosos
Dado un conjunto C de formas, se puede encontrar una aproximación a MDS ( C ) mediante el siguiente algoritmo codicioso :
- Inicialización: Inicializar un conjunto vacío, S .
- BÚSQUEDA: Para cada forma x en C :
- Calcule N (x) : el subconjunto de todas las formas en C que se cruzan con x (incluida la propia x ).
- Calcule el conjunto independiente más grande de este subconjunto: MDS (N (x)) .
- Seleccione una x tal que | MDS (N (x)) | se minimiza.
- Añadir x de S .
- Eliminar x y N (X) de C .
- Si hay formas en C , vuelva a Buscar.
- END: devolver el conjunto S .
Por cada forma x que agregamos a S , perdemos las formas en N (x) , porque están intersectadas por x y, por lo tanto, no se pueden agregar 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 MDS (S) . El subconjunto más grande de formas que pueden estar en la solución óptima es MDS (N (x)) . Por lo tanto, seleccionando una x que minimice | MDS (N (x)) | minimiza la pérdida de la adición de x a S .
En particular, si podemos garantizar que hay una x para la cual | MDS (N (x)) | está limitado por una constante (digamos, M ), entonces este algoritmo codicioso produce una aproximación constante del factor M , ya que podemos garantizar que:
Tal límite superior M existe para varios casos interesantes:
Intervalos unidimensionales: algoritmo polinomial exacto
Cuando C es un conjunto de intervalos en una línea, M = 1 y, por lo tanto, el algoritmo codicioso encuentra el MDS exacto. Para ver esto, asuma wlog 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 MDS (N (x)) tiene un tamaño de como máximo 1 (ver figura).
Por lo tanto, en el caso unidimensional, la MDS se puede encontrar exactamente en el tiempo O ( n log n ): [2]
- Ordene los intervalos en orden ascendente de sus puntos finales inferiores (esto lleva tiempo O ( n log n )).
- Agregue un intervalo con el punto final inferior más alto y elimine todos los intervalos que lo cruzan.
- Continúe hasta que no queden intervalos.
Este algoritmo es análogo a la primera solución de programación de la primera fecha límite para el problema de programación de intervalos .
En contraste con el caso unidimensional, en 2 o más dimensiones el problema MDS se vuelve NP-completo y, por lo tanto, tiene algoritmos superpolinomiales exactos o algoritmos polinomiales aproximados.
Formas de grasa: aproximaciones de factor constante
Cuando C es un conjunto de discos unitarios, M = 3, [3] porque el disco más a la izquierda (el disco cuyo centro tiene la coordenada x más pequeña ) se cruza como máximo con otros 3 discos disjuntos (ver figura). Por lo tanto, el algoritmo codicioso produce una aproximación de 3, es decir, encuentra un conjunto disjunto con un tamaño de al menos MDS (C) / 3.
De manera similar, cuando C es un conjunto de cuadrados unitarios paralelos al eje, 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 se cruza como máximo con otros 5 discos separados (ver figura).
De manera similar, cuando C es un conjunto de cuadrados paralelos al eje de tamaño arbitrario, M = 4.
Se pueden calcular otras constantes para otros polígonos regulares . [3]
Algoritmos de divide y vencerás
El enfoque más común para encontrar un MDS es dividir y conquistar. Un algoritmo típico en este enfoque tiene el siguiente aspecto:
- Divida el conjunto de formas dado en dos o más subconjuntos, de modo que las formas de cada subconjunto no puedan superponerse a las formas de otros subconjuntos debido a consideraciones geométricas.
- Encuentre de forma recursiva la MDS en cada subconjunto por separado.
- Devuelve la unión de las MDS de todos los subconjuntos.
El principal desafío con 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.
Rectángulos paralelos a los ejes con la misma altura: aproximación 2
Sea C un conjunto de n rectángulos paralelos al eje 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 | MDS ( C ) | / 2 en el tiempo O ( n log n ): [2]
- Dibuja m líneas horizontales, de modo que:
- La separación entre dos líneas es estrictamente más de H .
- Cada línea interseca al menos un rectángulo (por lo tanto, m ≤ n ).
- Cada rectángulo está cruzado exactamente por una línea.
- Dado que la altura de todos los rectángulos es H , no es posible que un rectángulo esté intersecado por más de una línea. Por lo tanto, las líneas dividen el conjunto de rectángulos en m subconjuntos () - cada subconjunto incluye los rectángulos intersecados por una sola línea.
- Para cada subconjunto , calcula una MDS exacta usando el algoritmo codicioso unidimensional (ver arriba).
- Por construcción, los rectángulos en () puede intersecar solo rectángulos en o en . Por lo tanto, cada una de las dos uniones siguientes es un conjunto disjunto:
- Unión de MDS impares:
- Unión de MDS pares:
- Devuelve el mayor de estos dos sindicatos. Su tamaño debe ser al menos | MDS | / 2.
Rectángulos paralelos a los ejes con la misma altura: PTAS
Sea C un conjunto de n rectángulos paralelos al eje 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 | MDS ( C ) | / (1 + 1 / k ) en el tiempo O ( n 2 k −1 ), para cada constante k > 1. [2]
El algoritmo es una mejora de la aproximación 2 mencionada anteriormente, al combinar la programación dinámica con la técnica de desplazamiento de Hochbaum y Maass. [4]
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 a lo largo de una de las dimensiones. Esto también reduce el tiempo a n ^ O (1 / e). [5]
Rectángulos paralelos a los ejes: aproximación de factor logarítmico
Sea C un conjunto de n rectángulos paralelos al eje en el plano. El siguiente algoritmo encuentra un conjunto disjunto con un tamaño de al menos a tiempo : [2]
- INICIALIZACIÓN: ordena los bordes horizontales de los rectángulos dados por su coordenada y , y los bordes verticales por su coordenada x (este paso toma tiempo O ( n log n )).
- CONDICIÓN DE PARADA: Si hay como máximo n ≤ 2 formas, calcule la MDS directamente y regrese.
- PARTE RECURSIVA:
- Dejar ser la mediana x -coordinada.
- Divida los rectángulos de entrada en tres grupos de acuerdo con su relación con la línea : los que están completamente a su izquierda (), los que están completamente a su derecha (), y aquellos cruzados por él (). Por construcción, las cardinalidades de y son como máximo n / 2.
- Calcule de forma recursiva una MDS aproximada en () y en (), y calcule su unión. Por construcción, los rectángulos en y son todos disjuntos, entonces es un conjunto disjunto.
- Calcule una MDS exacta en (). Dado que todos los rectángulos en intersecar una sola línea vertical , este cálculo es equivalente a encontrar una MDS a partir de un conjunto de intervalos, y puede resolverse exactamente en el tiempo O (n log n) (ver arriba).
- Regresar ya sea o - cualquiera de ellos sea más grande.
Es demostrable por inducción que, en el último paso, o tener una cardinalidad de al menos .
El factor de aproximación se ha reducido a [6] y generalizado al caso en el que los rectángulos tienen diferentes pesos. [7]
Rectángulos paralelos a los ejes: aproximación de factor constante
Durante mucho tiempo, no se supo si existe una aproximación de factor constante para rectángulos paralelos al eje de diferentes longitudes y alturas. Se conjeturó que tal aproximación se podría encontrar usando cortes de guillotina . Particularmente, si existe una separación de guillotina de ejes-rectángulos paralelos en los quelos rectángulos están separados, luego se puede usar en un enfoque de programación dinámica para encontrar una aproximación de factor constante a la MDS. [8] : apartado 1.2
Hasta la fecha, no se sabe si existe tal separación de guillotina. Sin embargo, Joseph SB Mitchell ha presentado un algoritmo de aproximación de factor constante que utiliza una clase especial de cortes sin guillotina. [9]
Objetos gordos de idéntico tamaño: PTAS
Sea C un conjunto de n cuadrados o círculos de idéntico tamaño. Existe un esquema de aproximación de tiempo polinomial para encontrar un MDS usando una estrategia simple de cuadrícula desplazada. Encuentra una solución dentro de (1 - e ) del máximo en el tiempo n O (1 / e 2 ) tiempo y espacio lineal. [4] La estrategia se generaliza a cualquier colección de objetos gordos de aproximadamente el mismo tamaño (es decir, cuando la proporción de tamaño máximo a mínimo está limitada por una constante).
Objetos gordos con tamaños arbitrarios: PTAS
Sea C un conjunto de n objetos gordos (por ejemplo, cuadrados o círculos) de tamaños arbitrarios. Hay un PTAS para encontrar un MDS basado en la alineación de cuadrícula de varios niveles. Ha sido descubierto por dos grupos aproximadamente al mismo tiempo y descrito de dos formas diferentes.
La versión 1 encuentra un conjunto disjunto con un tamaño de al menos (1 - 1 / k ) 2 · | MDS ( C ) | en el tiempo n O ( k 2 ) , para cada constante k > 1: [10]
Escale los discos para que el disco más pequeño tenga un diámetro 1. Divida los discos en niveles, según el logaritmo de su tamaño. Es decir, el j -ésimo nivel contiene todos los discos con diámetro entre ( k + 1) j y ( k + 1) j +1 , para j ≤ 0 (el disco más pequeño está en el nivel 0).
Para cada nivel j , imponga una cuadrícula en el plano que consta de líneas que están ( k + 1) j +1 separadas entre sí. Por construcción, cada disco puede intersecar como máximo una línea horizontal y una línea vertical desde su nivel.
Para cada r , s entre 0 y k , defina D ( r , s ) como el subconjunto de discos que no están intersectados por ninguna línea horizontal cuyo índice módulo k sea r , ni por ninguna línea vertical cuyo índice módulo k sea s . Según el principio del casillero , hay al menos un par (r, s) tal que, es decir, podemos encontrar el MDS solo en D ( r , s ) y perder solo una pequeña fracción de los discos en la solución óptima:
- Para todos los k 2 valores posibles de r , s (0 ≤ r , s < k ), calcule D ( r , s ) usando programación dinámica .
- Devuelve el mayor de estos k 2 conjuntos.
La versión 2 encuentra un conjunto disjunto con un tamaño de al menos (1 - 2 / k ) · | MDS ( C ) | en el tiempo n O ( k ) , para cada constante k > 1. [5]
El algoritmo utiliza cuatro árboles desplazados . El concepto clave del algoritmo es la alineación con la cuadrícula de cuatro árboles. Un objeto de tamaño r se llama k-alineado (donde k ≥ 1 es una constante) si está dentro de una celda de cuatro árboles de tamaño como máximo kr ( R ≤ kr ).
Por definición, un objeto alineado con k que cruza el límite de una celda de un cuarto 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 cubrirse con 4 k cuadrados de tamaño R / k ; por lo tanto, el número de objetos gordos disjuntos que cruzan el límite de esa celda es como máximo 4 kc , donde c es una constante que mide el grosor de los objetos.
Por lo tanto, si todos los objetos son gordos y están alineados con k , es posible encontrar el conjunto disjunto máximo exacto en el tiempo n O ( kc ) usando un algoritmo de divide y vencerás. Comience con una celda de cuatro árboles que contenga todos los objetos. Luego, divídalo recursivamente en celdas de cuatro árboles más pequeñas, encuentre el máximo en cada celda más pequeña y combine los resultados para obtener el máximo en la celda más grande. Dado que el número de objetos gruesos disjuntos que cruzan el límite de cada celda de árbol cuádruple está limitado por 4 kc , podemos simplemente "adivinar" qué objetos cruzan el límite en la solución óptima, y luego aplicar dividir y conquistar a los objetos dentro.
Si casi todos los objetos están alineados con k , podemos descartar los objetos que no están alineados con k y encontrar un conjunto disjunto máximo de los objetos restantes en el tiempo n O ( k ) . 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 , podemos intentar hacerlos alineados con k cambiando la cuadrícula en múltiplos de (1 / k , 1 / k ). Primero, escale los objetos de manera que todos queden contenidos en el cuadrado unitario. Luego, considere k cambios 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}, considere un cambio de la cuadrícula en (j / k, j / k). Es posible probar que cada etiqueta estará alineada con 2 k para al menos k - 2 valores de j . Ahora, para cada j , descarte los objetos que no estén alineados con k en el desplazamiento ( j / k , j / k ) y encuentre un conjunto disjunto máximo de los objetos restantes. Llame a ese conjunto A ( j ). Llame al conjunto disjunto máximo real es A *. Luego:
Por lo tanto, el mayor A ( j ) 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 O ( k ) . Podemos hacer que el factor de aproximación sea tan pequeño como queramos, así que este es un PTAS .
Ambas versiones se pueden generalizar a las dimensiones d (con diferentes ratios de aproximación) y al caso ponderado.
Algoritmos de separadores geométricos
Varios algoritmos de divide y vencerás se basan en un cierto teorema del separador geométrico . Un separador geométrico es una línea o forma que separa un conjunto dado 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 los PTAS como los algoritmos exactos sub-exponenciales, como se explica a continuación.
Objetos gordos con tamaños arbitrarios: PTAS con separadores geométricos
Sea C un conjunto de n objetos gordos de tamaños arbitrarios. El siguiente algoritmo encuentra un conjunto disjunto con un tamaño de al menos (1 - O ( √ b )) · | MDS ( C ) | en el tiempo n O ( b ) , para cada constante b > 1. [5]
El algoritmo se basa en el siguiente teorema del separador geométrico, que se puede probar de manera similar a la prueba de la existencia de un separador geométrico para cuadrados disjuntos :
- Por cada conjunto C de objetos gordos, hay un rectángulo que divide C en tres subconjuntos de objetos: C adentro , C afuera y C límite , de manera que:
- | MDS ( C interior ) | ≤ a | MDS ( C ) |
- | MDS ( C exterior ) | ≤ a | MDS ( C ) |
- | MDS ( límite C ) | c √ | MDS ( C ) |
- Por cada conjunto C de objetos gordos, hay un rectángulo que divide C en tres subconjuntos de objetos: C adentro , C afuera y C límite , de manera que:
donde un y c son constantes. Si pudiéramos calcular MDS ( C ) exactamente, podríamos hacer que la constante a sea tan baja como 2/3 mediante una selección adecuada del rectángulo separador. Pero como solo podemos aproximar MDS ( C ) por un factor constante, la constante a debe ser mayor. Afortunadamente, a sigue siendo una constante independiente de | C |.
Este teorema del separador permite construir el siguiente PTAS:
Seleccione una constante b . Compruebe todas las combinaciones posibles de hasta b + 1 etiquetas.
- Si | MDS ( C ) | tiene un tamaño de b como máximo (es decir, todos los conjuntos de etiquetas b + 1 no están disjuntos), luego devuelva ese MDS y salga. Este paso lleva n O ( b ) tiempo.
- De lo contrario, use un separador geométrico para separar C en dos subconjuntos. Encontrar los MDS aproximados en C dentro y C fuera por separado, y devolver su combinación como los MDS aproximados en C .
Sea E ( m ) el error del algoritmo anterior cuando el tamaño óptimo de MDS es MDS ( 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, . Podemos hacer que el factor de aproximación sea tan pequeño como queramos mediante una selección adecuada de b .
Este PTAS es más eficiente en el espacio que el PTAS basado en quadtrees y puede manejar una generalización donde los objetos pueden deslizarse, pero no puede manejar el caso ponderado.
Discos con una relación de tamaño limitada: algoritmo subexponencial exacto
Sea C un conjunto de n discos, de modo que la relación entre el radio más grande y el radio más pequeño sea como máximo r . El siguiente algoritmo encuentra MDS ( C ) exactamente a tiempo. [11]
El algoritmo se basa en un separador geométrico anchura delimitada en el conjunto Q de los centros de todos los discos en C . Este teorema del separador permite construir el siguiente algoritmo exacto:
- Encuentre una línea de separación tal que como máximo 2 n / 3 centros estén a su derecha ( C derecha ), como máximo 2 n / 3 centros estén a su izquierda ( C izquierda ), y como máximo O ( √ n ) centros estén en un distancia de menos de r / 2 de la línea ( C int ).
- Considere todos los posibles subconjuntos no superpuestos de C int . Hay como máximotales subconjuntos. Para cada uno de estos subconjuntos, calcule recursivamente la MDS de C a la izquierda y la MDS de C a la derecha , y devuelva el conjunto combinado más grande.
El tiempo de ejecución de este algoritmo satisface la siguiente relación de recurrencia:
La solución a esta recurrencia es:
Algoritmos de búsqueda local
Pseudodiscos: un PTAS
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. (Tenga en cuenta que esta definición se refiere a una colección completa y no dice nada sobre las formas de los objetos específicos de la colección). Un conjunto de pseudodiscos tiene una complejidad de unión limitada , es decir, el número de puntos de intersección en el límite de la unión de todos los objetos es lineal en el número de objetos.
Sea C un pseudodisks-set con n objetos. El siguiente algoritmo de búsqueda local encuentra un conjunto disjunto de tamaño al menos a tiempo , para cada constante entera : [12]
- INICIALIZACIÓN: inicializar un conjunto vacío, .
- BÚSQUEDA: recorre todos los subconjuntos de cuyo tamaño está entre 1 y . Para cada uno de esos subconjuntos X :
- Verifique que X en sí sea independiente (de lo contrario, vaya al siguiente subconjunto);
- Calcular el conjunto Y de los objetos en S que se cruzan X .
- Si , luego quite Y de S e inserte X :.
- END: devolver el conjunto S .
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; lo difícil es probar la relación de aproximación. [12]
Ver también. [13]
Algoritmos de relajación de programación lineal
Pseudodiscos: un PTAS
Sea C un conjunto de pseudodiscos con n objetos y complejidad de unión u . Usando la relajación de programación lineal , es posible encontrar un conjunto disjunto de tamaño al menos. Esto es posible con un algoritmo aleatorio que tenga una alta probabilidad de éxito y tiempo de ejecución., o un algoritmo determinista con un tiempo de ejecución más lento (pero aún polinomial). Este algoritmo se puede generalizar al caso ponderado. [12]
Otras clases de formas para las que se conocen aproximaciones
- Segmentos de línea en el plano bidimensional. [13] [14]
- Objetos convexos bidimensionales arbitrarios . [13]
- Curvas con un número limitado de puntos de intersección. [14]
enlaces externos
- Algoritmos de aproximación para un conjunto máximo independiente de pseudodiscos : presentación de Sariel Har-Peled .
- Código Javascript para calcular el máximo exacto de conjuntos disjuntos de rectángulos .
Notas
- ^ Ravi, SS; Hunt, HB (1987). "Una aplicación del teorema del separador plano para contar problemas". Cartas de procesamiento de información . 25 (5): 317. doi : 10.1016 / 0020-0190 (87) 90206-7 ., Smith, WD; Wormald, Carolina del Norte (1998). "Teoremas y aplicaciones del separador geométrico" . Actas 39º Simposio Anual sobre Fundamentos de la Informática (Cat. No.98CB36280) . pag. 232. doi : 10.1109 / sfcs.1998.743449 . ISBN 978-0-8186-9172-0. S2CID 17962961 .
- ^ a b c d Agarwal, PK; Van Kreveld, M .; Suri, S. (1998). "Colocación de etiquetas por máximo conjunto independiente en rectángulos". Geometría computacional . 11 (3–4): 209. doi : 10.1016 / s0925-7721 (98) 00028-5 . hdl : 1874/18908 .
- ^ a b Marathe, MV; Breu, H .; Hunt, HB; Ravi, SS; Rosenkrantz, DJ (1995). "Heurística simple para gráficos de disco unitario". Redes . 25 (2): 59. arXiv : math / 9409226 . doi : 10.1002 / net.3230250205 .
- ^ a b Hochbaum, DS ; Maass, W. (1985). "Esquemas de aproximación para cubrir y empaquetar problemas en procesamiento de imágenes y VLSI". Revista de la ACM . 32 : 130-136. doi : 10.1145 / 2455.214106 . S2CID 2383627 .
- ^ a b c Chan, TM (2003). "Esquemas de aproximación de polinomio-tiempo para empaquetar y perforar objetos grasos". Revista de algoritmos . 46 (2): 178–189. CiteSeerX 10.1.1.21.5344 . doi : 10.1016 / s0196-6774 (02) 00294-8 .
- ^ Chalermsook, P .; Chuzhoy, J. (2009). "Máximo conjunto independiente de rectángulos". Actas del vigésimo simposio anual ACM-SIAM sobre algoritmos discretos . pag. 892. doi : 10.1137 / 1.9781611973068.97 . ISBN 978-0-89871-680-1.
- ^ Chalermsook, P. (2011). "Colorear y conjunto máximo independiente de rectángulos". Aproximación, Aleatorización y Optimización Combinatoria. Algoritmos y Técnicas . Apuntes de conferencias en informática. 6845 . págs. 123-134. doi : 10.1007 / 978-3-642-22935-0_11 . ISBN 978-3-642-22934-3.
- ^ Abed, Fidaa; Chalermsook, Parinya; Correa, José; Karrenbauer, Andreas; Pérez-Lantero, Pablo; Soto, José A .; Wiese, Andreas (2015). Sobre secuencias de corte de guillotina . págs. 1–19. doi : 10.4230 / LIPIcs.APPROX-RANDOM.2015.1 . ISBN 978-3-939897-89-7.
- ^ Mitchell, Joseph SB (25 de junio de 2021). "Aproximación del conjunto independiente máximo para rectángulos en el plano". arXiv : 2101.00326 [ cs.CG ].
- ^ Erlebach, T .; Jansen, K .; Seidel, E. (2005). "Esquemas de aproximación de polinomio-tiempo para gráficos de intersección geométrica". Revista SIAM de Computación . 34 (6): 1302. doi : 10.1137 / s0097539702402676 .
- ^ Fu, B. (2011). "Teoría y aplicación de separadores geométricos acotados en ancho" . Revista de Ciencias de la Computación y Sistemas . 77 (2): 379–392. doi : 10.1016 / j.jcss.2010.05.003 .
- ^ a b c Chan, TM ; Har-Peled, S. (2012). "Algoritmos de aproximación para el conjunto máximo independiente de pseudodiscos". Geometría discreta y computacional . 48 (2): 373. arXiv : 1103.1431 . doi : 10.1007 / s00454-012-9417-5 . S2CID 38183751 .
- ^ a b c Agarwal, PK; Mustafa, NH (2006). "Conjunto independiente de gráficos de intersección de objetos convexos en 2D" . Geometría computacional . 34 (2): 83. doi : 10.1016 / j.comgeo.2005.12.001 .
- ^ a b Fox, J .; Pach, JN (2011). "Cálculo del número de independencia de gráficos de intersección". Actas del Vigésimo Segundo Simposio Anual ACM-SIAM sobre Algoritmos Discretos . pag. 1161. CiteSeerX 10.1.1.700.4445 . doi : 10.1137 / 1.9781611973082.87 . ISBN 978-0-89871-993-2. S2CID 15850862 .