Conjunto disjunto máximo

En geometría computacional , un conjunto disjunto máximo ( MDS ) es el 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 conjuntos independientes máximos es un caso especial del problema de conjuntos independientes máximos (MIS) . Ambos problemas son NP completos , pero encontrar un conjunto independiente máximo 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 los exponenciales. En algunos gráficos de intersección geométrica, existen algoritmos subexponenciales para hallar una 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 polinomial (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 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 ) denota el conjunto máximo disjunto en un conjunto C .

Dado un conjunto C de formas, se puede encontrar una aproximación a MDS( C ) mediante el siguiente algoritmo voraz :

• INICIALIZACIÓN: Inicializa un conjunto vacío , S.
• BUSCAR: Para cada figura xi en C :
  1. Calcula J(xi), el subconjunto de todas las formas en C que intersecan xi (incluyendo xi mismo).
  2. Asigna N(xi) igual al número de formas en J(xi).
  3. Elija cualquier xj tal que N(xj) sea un máximo, es decir, una forma que toque tantas formas como cualquier otra.
  4. De todas las formas xi que intersecan a xj (incluida la propia xj), seleccione la forma x que toque menos otras formas, es decir, x tal que. N(x) es un mínimo
• Añade x a S.​
• Elimina x de C y elimina J(x) y N(x)
• Si hay formas en C , regrese a Buscar.
• FIN : devuelve el conjunto S.

Por cada forma x que añadimos a S , perdemos las formas en N(x) , porque son intersectadas por x y por lo tanto no pueden añadirse a S más adelante. Sin embargo, algunas de estas formas se intersecan 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 todas en la solución óptima es MDS(N(x)) . Por lo tanto, seleccionar una x que minimice |MDS(N(x))| minimiza la pérdida por añadir x a S .

En particular, si podemos garantizar que hay una x para la cual |MDS(N(x))| está limitada por una constante (por ejemplo, M ), entonces este algoritmo codicioso produce una aproximación de factor M constante , ya que podemos garantizar que:

${\displaystyle |S|\geq {\frac {|MDS(C)|}{M}}}$

Este límite superior M existe para varios casos interesantes:

Cuando C es un conjunto de intervalos en una línea, M = 1, y por lo tanto el algoritmo voraz encuentra el MDS exacto. Para ver esto, supongamos que wlog los intervalos son verticales, y sea x el intervalo con el punto extremo inferior más alto . Todos los demás intervalos intersectados por x deben cruzar su punto extremo inferior. Por lo tanto, todos los intervalos en N(x) se intersecan 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]

1. Ordene los intervalos en orden ascendente de sus puntos finales inferiores (esto lleva tiempo O ( n  log  n )).
2. Agregue un intervalo con el punto final inferior más alto y elimine todos los intervalos que lo intersecan.
3. Continúe hasta que no queden intervalos.

Este algoritmo es análogo a la solución de programación de fecha límite más temprana para el problema de programación de intervalos .

A diferencia del 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.

Cuando C es un conjunto de discos unitarios, M = 3, ^[3] porque el disco situado 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 figura). Por lo tanto, el algoritmo voraz 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 intersecta como máximo otros 5 discos disjuntos (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]

El método más común para encontrar un MDS es dividir y vencer. Un algoritmo típico de este método es el siguiente:

1. 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.
2. Encuentre recursivamente el MDS en cada subconjunto por separado.
3. Devuelve la unión de los MDS de todos los subconjuntos.

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 |MDS( C )|/2 en tiempo O ( n  log  n ): ^[2]

• Dibuje m líneas horizontales, tales que:
  1. La separación entre dos líneas es estrictamente mayor que H.
  2. Cada línea interseca al menos un rectángulo (por lo tanto, m  ≤  n ).
  3. Cada rectángulo está intersectado exactamente por una línea.
• Como la altura de todos los rectángulos es H , no es posible que un rectángulo sea 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.${\displaystyle R_{i},\ldots ,R_{m}}$
• Para cada subconjunto , calcule un MDS exacto utilizando el algoritmo voraz unidimensional (ver arriba).${\displaystyle R_{i}}$$Estilo de visualización M_{i}}$
• Por construcción, los rectángulos en ( ) pueden intersecar solo los rectángulos en o en . Por lo tanto, cada una de las dos siguientes uniones es un conjunto disjunto: ${\displaystyle R_{i}}$$Estilo de visualización R_{i+1}}$$Estilo de visualización R_{i-1}}$
  • Unión de MDS impares:${\displaystyle M_{1}\cup M_{3}\cup \cdots }$
  • Unión de MDS pares:${\displaystyle M_{2}\cup M_{4}\cup \cdots }$
• Devuelve la mayor de estas dos uniones. Su tamaño debe ser al menos |MDS|/2.

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 |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]

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 en el tiempo : ^[2]${\displaystyle {\frac {|MDS(C)|}{\log {n}}}}$${\displaystyle O(n\log {n})}$

• INICIALIZACIÓN: ordenar 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 el MDS directamente y regrese.
• PARTE RECURSIVA:
  1. Sea la mediana de la coordenada x .${\displaystyle x_{\mathrm {med} }}$
  2. Divida los rectángulos de entrada en tres grupos según su relación con la línea : aquellos que están completamente a su izquierda ( ), aquellos que están completamente a su derecha ( ) y aquellos que son intersectados por ella ( ). Por construcción, las cardinalidades de y son como máximo n /2.${\displaystyle x=x_{\mathrm {med}}}$${\displaystyle R_{\mathrm {izquierda}}}$${\displaystyle R_{\mathrm {derecha} }}$${\displaystyle R_{\mathrm {int} }}$${\displaystyle R_{\mathrm {izquierda}}}$${\displaystyle R_{\mathrm {derecha} }}$
  3. Calcular recursivamente una MDS aproximada en ( ) y en ( ), y calcular su unión. Por construcción, los rectángulos en y son todos disjuntos, por lo que es un conjunto disjunto.${\displaystyle R_{\mathrm {izquierda}}}$${\displaystyle M_{\mathrm {izquierda}}}$${\displaystyle R_{\mathrm {derecha} }}$${\displaystyle M_{\mathrm {derecha}}}$${\displaystyle M_{\mathrm {izquierda}}}$${\displaystyle M_{\mathrm {derecha}}}$${\displaystyle M_{\mathrm {izquierda} }\cup M_{\mathrm {derecha} }}$
  4. Calcule una MDS exacta en ( ). Dado que todos los rectángulos en intersecan una única línea vertical , este cálculo es equivalente a hallar una MDS a partir de un conjunto de intervalos y se puede resolver exactamente en tiempo O(n log n) (ver arriba).${\displaystyle R_{\mathrm {int} }}$${\displaystyle M_{\mathrm {int} }}$${\displaystyle R_{\mathrm {int} }}$${\displaystyle x=x_{\mathrm {med}}}$
• Devuelve uno o ambos , cualquiera que sea mayor.${\displaystyle M_{\mathrm {izquierda} }\cup M_{\mathrm {derecha} }}$${\displaystyle M_{\mathrm {int} }}$

Se puede demostrar por inducción que, en el último paso, o bien o bien tienen una cardinalidad de al menos . ${\displaystyle M_{\mathrm {izquierda} }\cup M_{\mathrm {derecha} }}$${\displaystyle M_{\mathrm {int} }}$${\displaystyle {\frac {|MDS(C)|}{\log {n}}}}$

Chalermsookk y Chuzoy ^[6] han mejorado el factor a . ${\displaystyle O(\log {\log {n}})}$

Chalermsook y Walczak ^[7] han presentado un algoritmo de aproximación al 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. ${\displaystyle O(\log {\log {n}})}$

Durante mucho tiempo, no se supo si existía una aproximación de factor constante para rectángulos paralelos a los ejes de diferentes longitudes y alturas. Se conjeturó que tal aproximación podría encontrarse utilizando cortes de guillotina . En particular, si existe una separación de guillotina de rectángulos paralelos a los ejes en la que los rectángulos están separados, entonces se puede utilizar en un enfoque de programación dinámica para encontrar una aproximación de factor constante a la MDS. ^{[8] : sub.1.2}${\displaystyle \Omega (n)}$

Hasta el momento no se sabe si existe una separación de este tipo mediante guillotina. Sin embargo, existen algoritmos de aproximación de factor constante que utilizan cortes distintos de la guillotina:

• Joseph SB Mitchell presentó un algoritmo de aproximación de 10 factores. Su algoritmo se basa en la partición del plano en rectángulos recortados en sus esquinas . ^[9]
• Gálvez, Khan, Mari, Mömke, Pittu y Wiese presentaron un algoritmo que divide el plano en una clase más general de polígonos. Esto simplifica el análisis y mejora la aproximación a 6 factores. Además, mejoraron la aproximación a 3 factores ^[10] y luego a (2+ε)-factor. ^[11]

Sea C un conjunto de n cuadrados o círculos de idéntico tamaño. Hochbaum y Maass ^[4] presentaron un esquema de aproximación de tiempo polinomial para encontrar una MDS utilizando una estrategia de cuadrícula desplazada simple. Encuentra una solución dentro de (1 − ε) del máximo en el tiempo n ^{O (1/ ε 2 )} tiempo y espacio lineal. La estrategia se generaliza a cualquier colección de objetos gordos 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 PTAS para encontrar un MDS basado en la alineación de cuadrícula de múltiples niveles. Ha sido descubierto por dos grupos aproximadamente al mismo tiempo y descrito de dos maneras diferentes.

Un algoritmo de Erlebach, Jansen y Seidel ^[12] encuentra un conjunto disjunto con un tamaño de al menos (1 − 1/ k ) ²  ⋅ |MDS( C )| en el tiempo n ^{O ( k 2 )} , para cada constante k  > 1. Funciona de la siguiente manera.

Escalar los discos de manera que el disco más pequeño tenga un diámetro de 1. Dividir los discos en niveles, en función del logaritmo de su tamaño. Es decir, el nivel j contiene todos los discos con un 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 , se impone una cuadrícula en el plano que consta de líneas que están separadas ( k  + 1) ^{j +1} 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 , definamos D ( r , s ) como el subconjunto de discos que no son 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 . Por el principio del palomar , existe al menos un par (r,s) tal que , es decir, podemos encontrar la MDS solo en D ( r , s ) y omitir solo una pequeña fracción de los discos en la solución óptima: ${\displaystyle |\mathrm {MDS} (D(r,s))|\geq (1-{\frac {1}{k}})^{2}\cdot |\mathrm {MDS} |}$

• Para todos los k ² valores posibles de r , s (0 ≤  r , s  <  k ), calcule D ( r , s ) utilizando programación dinámica .
• Devuelve el mayor de estos k ² conjuntos.

Un algoritmo de Chan ^[5] 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.

El algoritmo utiliza quadtrees desplazados . El concepto clave del algoritmo es la alineación con la cuadrícula de quadtrees. Un objeto de tamaño r se denomina k-alineado (donde k  ≥ 1 es una constante) si está dentro de una celda de quadtree de tamaño kr como máximo ( R  ≤  kr ).

Por definición, un objeto alineado con k que interseca el límite de una celda de un árbol de cuatro dimensiones 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 4 k cuadrados de tamaño R / k ; por lo tanto, la cantidad de objetos gordos disjuntos que intersecan el límite de esa celda es como máximo 4 kc , donde c es una constante que mide la gordura 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 )} utilizando un algoritmo de dividir y vencer. Comience con una celda de árbol cuaternario que contenga todos los objetos. Luego, divídala recursivamente en celdas de árbol cuaternario 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 gordos disjuntos que intersecan el límite de cada celda de árbol cuaternario está limitado por 4 kc , podemos simplemente "adivinar" qué objetos intersecan el límite en la solución óptima y luego aplicar el algoritmo de dividir y vencer 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 k -alineados, podemos intentar hacerlos k -alineados desplazando la cuadrícula en múltiplos de (1/ k ,1/ k ). Primero, escalamos los objetos de modo que todos estén contenidos en el cuadrado unitario. Luego, consideramos 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}, consideramos un desplazamiento de la cuadrícula en (j/k,j/k). Es posible demostrar que cada etiqueta estará 2 k -alineada para al menos k  − 2 valores de  j . Ahora, para cada j , descartamos los objetos que no están k -alineados en el desplazamiento ( j / k , j / k ), y encontramos un conjunto disjunto máximo de los objetos restantes. Llamamos a ese conjunto A ( j ). Llamemos al conjunto real máximo disjunto  A *. Entonces:

${\displaystyle \sum_{j=0,\ldots,k-1}{|A(j)|}\geq (k-2)|A*|}$

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 A ( j ) más grande; 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, por lo que este es un PTAS .

Ambas versiones pueden generalizarse a dimensiones d (con diferentes razones de aproximación) y al caso ponderado.

Varios algoritmos de divide y vencerás se basan en un determinado teorema de separador geométrico . Un separador geométrico es una línea o figura que separa un conjunto dado de figuras en dos subconjuntos más pequeños, de modo que la cantidad de figuras perdidas durante la división sea relativamente pequeña. Esto permite tanto los algoritmos PTAS como los algoritmos exactos subexponenciales, como se explica a continuación.

Sea C un conjunto de n objetos gordos , como cuadrados o círculos, de tamaños arbitrarios. Chan ^[5] describió un algoritmo que 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.

El algoritmo se basa en el siguiente teorema del separador geométrico, que puede demostrarse de forma similar a la prueba de la existencia del separador geométrico para cuadrados disjuntos :

Para cada conjunto C de objetos gordos, hay un rectángulo que divide a C en tres subconjuntos de objetos: C _interior , C _exterior y C _límite , tales que:

• |MDS( C _dentro )| ≤ a |MDS( C )|
• |MDS( C _exterior )| ≤ a|MDS( C )|
• |MDS( C _límite )| c √ | MDS( C ) |

donde a y c son constantes. Si pudiéramos calcular MDS( C ) con exactitud, 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 ) mediante un factor constante, la constante a debe ser mayor. Afortunadamente, a sigue siendo una constante independiente de | C |.

Este teorema separador permite construir las siguientes PTAS:

Seleccione una constante b . Marque 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 b  + 1 etiquetas no son disjuntos), entonces simplemente devuelva ese MDS y salga. Este paso toma n ^{O ( b )} tiempo.
• De lo contrario, utilice un separador geométrico para separar C en dos subconjuntos. Encuentre la MDS aproximada en C _dentro y C _fuera por separado, y devuelva su combinación como la MDS aproximada 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 en c √ m el número de etiquetas intersectadas por el separador. El peor caso para el algoritmo es cuando la división en cada paso está en la razón máxima posible que es a :(1 −  a ). Por lo tanto, la función de error satisface la siguiente relación de recurrencia:

${\displaystyle E(m)=0\ \ \ \ {\text{si }}m\leq b}$

${\displaystyle E(m)=E(a\cdot m)+E((1-a)\cdot m)+c\cdot {\sqrt {m}}{\text{ si }}m>b}$

La solución a esta recurrencia es:

${\displaystyle E(m)=({\frac {0}{b}}+{\frac {c}{{\sqrt {b}}({\sqrt {a}}+{\sqrt {1-a}}-1)}})\cdot m-{\frac {c}{{\sqrt {a}}+{\sqrt {1-a}}-1}}\cdot {\sqrt {m}}.}$

es decir , podemos hacer que el factor de aproximación sea tan pequeño como queramos mediante una selección adecuada de b . ${\displaystyle E(m)=O(m/{\sqrt {b}})}$

Este PTAS es más eficiente en términos de espacio que el PTAS basado en árboles cuádruples, y puede manejar una generalización donde los objetos pueden deslizarse, pero no puede manejar el caso ponderado.

Sea C un conjunto de n discos, de modo que la relación entre el radio mayor y el radio menor sea como máximo r . El siguiente algoritmo encuentra MDS( C ) exactamente en el tiempo . ^[13]${\displaystyle 2^{O(r\cdot {\sqrt {n}})}}$

El algoritmo se basa en un separador geométrico limitado por la anchura en el conjunto Q de los centros de todos los discos en C. Este teorema del separador permite construir el siguiente algoritmo exacto:

• Encuentra una línea separadora 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 a una distancia menor que r /2 de la línea ( C _int ).
• Considere todos los subconjuntos posibles no superpuestos de C _int . Como máximo, existen subconjuntos de este tipo. Para cada uno de estos subconjuntos, calcule recursivamente la MDS de C _left y la MDS de C _right , y devuelva el conjunto combinado más grande.${\displaystyle 2^{O(r\cdot {\sqrt {n}})}}$

El tiempo de ejecución de este algoritmo satisface la siguiente relación de recurrencia:

${\displaystyle T(1)=1}$

${\displaystyle T(n)=2^{O(r\cdot {\sqrt {n}})}T\left({\frac {2n}{3}}\right){\text{ si }}n>1}$

La solución a esta recurrencia es:

${\displaystyle T(n)=2^{O(r\cdot {\sqrt {n}})}}$

Un pseudoconjunto de discos es un conjunto de objetos en el que los límites de cada par de objetos se intersecan como máximo dos veces (nótese que esta definición se relaciona con una colección completa y no dice nada sobre las formas de los objetos específicos de la colección). Un pseudoconjunto de discos 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 en el número de objetos. Por ejemplo, un conjunto de cuadrados o círculos de tamaños arbitrarios es un pseudoconjunto de discos.

Sea C un pseudoconjunto de discos con n objetos. Un algoritmo de búsqueda local de Chan y Har-Peled ^[14] encuentra un conjunto disjunto de tamaño al menos en el tiempo , para cada constante entera : ${\displaystyle (1-O({\frac {1}{\sqrt {b}}}))\cdot |MDS(C)|}$${\displaystyle O(n^{b+3})}$${\displaystyle b\geq 0}$

• INICIALIZACIÓN: Inicializa un conjunto vacío, .${\estilo de visualización S}$
• BÚSQUEDA: Recorrer todos los subconjuntos cuyo tamaño esté entre 1 y . Para cada uno de estos subconjuntos X : ${\estilo de visualización CS}$${\estilo de visualización b+1}$
  • Verifique que X en sí mismo sea independiente (de lo contrario, pase al siguiente subconjunto);
  • Calcular el conjunto Y de objetos en S que intersecan a X.
  • Si , entonces elimine Y de S e inserte X : .${\displaystyle |Y|<|X|}$${\displaystyle S:=S-Y+X}$
• FIN : devuelve 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 demostrar la razón de aproximación. ^[14]

Véase también. ^[15]

Sea C un pseudoconjunto de discos con n objetos y complejidad de unión u . Utilizando la relajación de programación lineal , es posible encontrar un conjunto disjunto de tamaño al menos . Esto es posible ya sea 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. ^[14]${\displaystyle {\frac {n}{u}}\cdot |MDS(C)|}$${\displaystyle O(n^{3})}$

• Segmentos de línea en el plano bidimensional. ^{[15] [16]}
• Objetos convexos bidimensionales arbitrarios . ^[15]
• Curvas con un número limitado de puntos de intersección. ^[16]

• Algoritmos de aproximación para el conjunto máximo independiente de pseudodiscos: presentación de Sariel Har-Peled .
• Código Javascript para calcular el conjunto disjunto máximo exacto de rectángulos.