Conjunto máximo disjunto

Concepto en geometría computacional.

En geometría computacional , un conjunto máximo disjunto ( 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 MDS es un caso especial del problema del conjunto máximo independiente (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 subexponenciales 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 en 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 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 disjunto máximo 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: Inicializa un conjunto vacío, S .
• BÚSQUEDA: Para cada forma xi en C :
  1. Calcule J(xi), el subconjunto de todas las formas en C que intersectan a xi (incluido el propio xi ).
  2. Asigne N(xi) igual a las formas numéricas 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 intersectan a xj (incluido el propio xj), seleccione la forma x que toca la menor cantidad de otras formas, es decir, x tal que. N(x) es un mínimo
• Suma x a S .
• Elimine x de C y elimine J(x) y N(x)
• Si hay formas en C , regrese a Buscar.
• FINAL: devuelve el conjunto S .

Por cada forma x que agregamos a S , perdemos las formas en N(x) , porque están intersecadas 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, seleccionar una x que minimice |MDS(N(x))| minimiza la pérdida al agregar x a S .

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

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

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

Intervalos unidimensionales: algoritmo polinómico 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, supongamos 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, el 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 cruzan.
3. Continúe hasta que no queden intervalos.

Este algoritmo es análogo a la solución de primera programación con fecha límite más temprana para el problema de programación por 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 gordas: 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 ) intersecta como máximo otros 3 discos disjuntos (ver figura). Por lo tanto, el algoritmo codicioso produce una aproximación 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]

Algoritmos de divide y vencerás

El enfoque más común para encontrar un MDS es dividir y vencerás. Un algoritmo típico de este enfoque se parece al 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.

Rectángulos paralelos al eje con la misma altura: 2-aproximación

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, tales que:
  1. La separación entre dos líneas es estrictamente mayor que H .
  2. Cada línea cruza al menos un rectángulo (por lo tanto, m  ≤  n ).
  3. Cada rectángulo está intersecado por exactamente una línea.
• Dado que la altura de todos los rectángulos es H , no es posible que un rectángulo sea interceptado 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 codicioso unidimensional (ver arriba). ${\displaystyle R_{i}}$ ${\displaystyle M_{i}}$
• Por construcción, los rectángulos en ( ) solo pueden intersecar rectángulos en o en . Por lo tanto, cada una de las dos uniones siguientes es un conjunto disjunto: ${\displaystyle R_{i}}$ ${\displaystyle R_{i+1}}$ ${\displaystyle 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.

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

• INICIALIZACIÓN: ordene los bordes horizontales de los rectángulos dados por su coordenada y , y los bordes verticales por su coordenada x (este paso lleva tiempo O ( n  log  n )).
• CONDICIÓN DE DETENCIÓN: Si hay como máximo n  ≤ 2 formas, calcule el MDS directamente y regrese.
• PARTE RECURSIVA:
  1. Sea la coordenada x mediana . ${\displaystyle x_{\mathrm {med} }}$
  2. Divida los rectángulos de entrada en tres grupos según su relación con la línea : los que están completamente a la izquierda ( ), los que están completamente a la derecha ( ) y los que intersecan ( ). Por construcción, las cardinalidades de y son como máximo n /2. ${\displaystyle x=x_{\mathrm {med} }}$ ${\displaystyle R_{\mathrm {left} }}$ ${\displaystyle R_{\mathrm {right} }}$ ${\displaystyle R_{\mathrm {int} }}$ ${\displaystyle R_{\mathrm {left} }}$ ${\displaystyle R_{\mathrm {right} }}$
  3. Calcule recursivamente un MDS aproximado en ( ) y en ( ), y calcule su unión. Por construcción, los rectángulos en y son todos disjuntos, por lo que también lo es un conjunto disjunto. ${\displaystyle R_{\mathrm {left} }}$ ${\displaystyle M_{\mathrm {left} }}$ ${\displaystyle R_{\mathrm {right} }}$ ${\displaystyle M_{\mathrm {right} }}$ ${\displaystyle M_{\mathrm {left} }}$ ${\displaystyle M_{\mathrm {right} }}$ ${\displaystyle M_{\mathrm {left} }\cup M_{\mathrm {right} }}$
  4. Calcule una MDS exacta en ( ). Dado que todos los rectángulos se cruzan con una sola línea vertical , este cálculo es equivalente a encontrar un MDS a partir de un conjunto de intervalos y se puede resolver exactamente en el 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 cualquiera de los dos o el que sea mayor. ${\displaystyle M_{\mathrm {left} }\cup M_{\mathrm {right} }}$ ${\displaystyle M_{\mathrm {int} }}$

Es demostrable por inducción que, en el último paso, o tienen una cardinalidad de al menos . ${\displaystyle M_{\mathrm {left} }\cup M_{\mathrm {right} }}$ ${\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}})}$

Rectángulos paralelos al eje: aproximación de factor constante

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 mediante cortes de guillotina . En particular, si existe una separación de guillotina de rectángulos paralelos a los ejes en los 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 al MDS. ^{[8] : sub.1.2} ${\displaystyle \Omega (n)}$

Hasta la fecha no se sabe si existe tal separación de guillotina. Sin embargo, existen algoritmos de aproximación de factor constante que utilizan cortes sin guillotina:

• Joseph SB Mitchell presentó un algoritmo de aproximación de 10 factores. Su algoritmo se basa en dividir el plano en rectángulos recortados en las 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 al factor 3 ^[10] y luego al factor (2+ε). ^[11]

Objetos gordos de idéntico tamaño: PTAS

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 en tiempo polinomial para encontrar una MDS utilizando una estrategia simple de cuadrícula desplazada. Encuentra una solución dentro de (1 − ε) del máximo en 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).

Objetos gordos con tamaños arbitrarios: PTAS

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 la cuadrícula de varios niveles. Ha sido descubierto por dos grupos aproximadamente al mismo tiempo y descrito de dos maneras diferentes.

partición de nivel

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.

Escale los discos para que el disco más pequeño tenga un diámetro de 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 cruzar 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 son intersecados 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 sólo en D ( r , s ) y perder sólo 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 ) usando programación dinámica .
• Devuelve el mayor de estos k ² conjuntos.

Árboles cuádruples desplazados

Un árbol cuádruple de región con datos de puntos.

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 quadtree. 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 k alineado que cruza 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 4 k 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 4 kc , donde c es una constante que mide la gordura de los objetos.

Por lo tanto, si todos los objetos están alineados y alineados con k , es posible encontrar el conjunto disjunto máximo exacto en el tiempo n ^{O ( kc )} utilizando un algoritmo de divide y vencerás. Comience con una celda de árbol cuádruple que contenga todos los objetos. Luego, divídalo de forma recursiva 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 del á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 divide y vencerás a los objetos internos.

Si casi todos los objetos están alineados con k , podemos simplemente 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 k -alineados.

Si la mayoría de los objetos no están alineados con k , podemos intentar alinearlos con k cambiando la cuadrícula en múltiplos de (1/ k ,1/ k ). Primero, escale los objetos de modo que todos estén contenidos en el cuadrado unitario. Luego, considere 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}, considere un desplazamiento de la cuadrícula en (j/k,j/k). Es posible demostrar 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 k alineados en el desplazamiento ( j / k , j / k ) y encuentre un conjunto máximo disjunto de los objetos restantes. Llame a ese conjunto A ( j ). Llame al conjunto disjunto máximo real es  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 )| Un *|. 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, por lo que este es un PTAS .

Ambas versiones se pueden generalizar a dimensiones d (con diferentes relaciones de aproximación) y al caso ponderado.

Algoritmos de separador geométrico

Varios algoritmos de divide y vencerás se basan en un determinado 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 PTAS como algoritmos exactos subexponenciales, como se explica a continuación.

Objetos gordos con tamaños arbitrarios: PTAS usando separadores geométricos

Sea C un conjunto de n objetos gruesos , 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 se puede demostrar de manera similar a la prueba de la existencia de un separador geométrico para cuadrados disjuntos :

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

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

donde a 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 sólo 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 del separador permite construir los siguientes PTAS:

Seleccione una constante b . Consulta todas las combinaciones posibles de hasta b  +1 etiquetas.

• Si |MDS( C )| tiene un tamaño de como máximo b (es decir, todos los conjuntos de etiquetas b  + 1 no están separados), luego simplemente devuelva ese MDS y salga. Este paso lleva n ^{O ( b )} tiempo.
• De lo contrario, utilice un separador geométrico para separar C en dos subconjuntos. Encuentre el MDS aproximado en C interior _y C exterior _por separado y devuelva su combinación como el MDS aproximado 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:

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

${\displaystyle E(m)=E(a\cdot m)+E((1-a)\cdot m)+c\cdot {\sqrt {m}}{\text{ if }}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 ahorra más espacio que el PTAS basado en quadtrees y puede manejar una generalización en la que 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, tal 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 en el tiempo . ^[13] ${\displaystyle 2^{O(r\cdot {\sqrt {n}})}}$

El algoritmo se basa en un separador geométrico de ancho limitado 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 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 en un distancia inferior a r /2 de la línea ( C _int ).
• Considere todos los posibles subconjuntos no superpuestos de C _int . Como máximo existen subconjuntos de este tipo. Para cada uno de estos subconjuntos, calcule recursivamente el MDS de C _left y el 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{ if }}n>1}$

La solución a esta recurrencia es:

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

Algoritmos de búsqueda locales

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 relaciona con 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. 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 ^[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, . ${\displaystyle S}$
• BÚSQUEDA: recorra todos los subconjuntos cuyo tamaño esté entre 1 y . Para cada uno de esos subconjuntos X : ${\displaystyle C-S}$ ${\displaystyle b+1}$
  • Verifique que el propio X sea independiente (de lo contrario, pase al siguiente subconjunto);
  • Calcula el conjunto Y de objetos en S que intersectan a X.
  • Si , entonces elimine Y de S e inserte X :. ${\displaystyle |Y|<|X|}$ ${\displaystyle S:=S-Y+X}$
• FINAL: 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; La parte difícil es demostrar la relación de aproximación. ^[14]

Ver también. ^[15]

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 . Utilizando la relajación de la programación lineal , es posible encontrar un conjunto disjunto de tamaño al menos . Esto es posible con un algoritmo aleatorio que tiene una alta probabilidad de éxito y tiempo de ejecución , o con 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})}$

Otras clases de formas para las que se conocen aproximaciones

• Segmentos de recta en el plano bidimensional. ^{[15] [16]}
• Objetos convexos bidimensionales arbitrarios . ^[15]
• Curvas con un número acotado de puntos de intersección. ^[dieciséis]

enlaces externos

• 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 máximo exacto de rectángulos disjuntos.

Notas

1. Ravi, SS; Cazar, HB (1987). "Una aplicación del teorema del separador plano a problemas de conteo". 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 del 39º Simposio anual sobre fundamentos de la informática (n.º de catálogo 98CB36280) . pag. 232. doi : 10.1109/sfcs.1998.743449. ISBN 978-0-8186-9172-0. S2CID  17962961.
2. 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 .
3. Marathe, MV; Breu, H.; Cazar, HB; Ravi, SS; Rosenkrantz, DJ (1995). "Heurística simple para gráficos de discos unitarios". Redes . 25 (2): 59. arXiv : matemáticas/9409226 . doi :10.1002/net.3230250205.
4. Hochbaum, DS ; Maass, W. (1985). "Esquemas de aproximación para problemas de cobertura y empaquetamiento en procesamiento de imágenes y VLSI". Revista de la ACM . 32 : 130-136. doi : 10.1145/2455.214106 . S2CID  2383627.
5. Chan, TM (2003). "Esquemas de aproximación en tiempo polinómico 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. 
6. Chalermsook, P.; Chuzhoy, J. (2009). "Conjunto máximo 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.
7. Chalermsook, Parinya; Walczak, Bartosz (1 de enero de 2021), "Conjunto de rectángulos independientes del color y el peso máximo", Actas del Simposio ACM-SIAM de 2021 sobre algoritmos discretos (SODA) , Actas, Sociedad de Matemáticas Industriales y Aplicadas, págs. 868, arXiv : 2007.07880 , doi : 10.1137/1.9781611976465.54 , ISBN 978-1-61197-646-5, S2CID  220525811
8. Abed, Fidaa; Chalermsook, Parinya; Correa, José; Karrenbauer, Andreas; Pérez-Lantero, Pablo; Soto, José A.; Wiese, Andreas (2015). Sobre secuencias de corte con guillotina. págs. 1-19. doi :10.4230/LIPIcs.APPROX-RANDOM.2015.1. ISBN 978-3-939897-89-7.
9. Mitchell, Joseph SB (25 de junio de 2021). "Conjunto independiente máximo aproximado para rectángulos en el plano". arXiv : 2101.00326 [cs.CG].
10. Gálvez, Waldo; Khan, Arindam; Mari, Mathieu; Mömke, Tobías; Pittu, Madhusudhan Reddy; Wiese, Andreas (1 de enero de 2022), "Un algoritmo de 3 aproximaciones para un conjunto máximo de rectángulos independientes", Actas del Simposio anual ACM-SIAM de 2022 sobre algoritmos discretos (SODA) , Actas, Sociedad de Matemáticas Industriales y Aplicadas, págs. 894–905, doi :10.1137/1.9781611977073.38, ISBN 978-1-61197-707-3, S2CID  235265867 , consultado el 29 de septiembre de 2022
11. Gálvez, Waldo; Khan, Arindam; Mari, Mathieu; Mömke, Tobías; Reddy, Madhusudhan; Wiese, Andreas (26 de septiembre de 2021). "Un algoritmo de aproximación (2+\epsilon) para el conjunto máximo independiente de rectángulos". arXiv : 2106.00623 [cs.CG].
12. Erlebach, T.; Jansen, K.; Seidel, E. (2005). "Esquemas de aproximación en tiempo polinomial para gráficos de intersección geométrica". Revista SIAM de Computación . 34 (6): 1302. doi : 10.1137/s0097539702402676.
13. Fu, B. (2011). "Teoría y aplicación de separadores geométricos acotados en ancho". Revista de Ciencias de la Computación y de Sistemas . 77 (2): 379–392. doi : 10.1016/j.jcss.2010.05.003 .
14. 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.
15. Agarwal, PK; Mustafa, Nueva Hampshire (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.
16. 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.