Separador geométrico

Un separador geométrico es una línea (u otra forma) que divide una colección de formas geométricas en dos subconjuntos, de modo que la proporción de formas en cada subconjunto está limitada y el número de formas que no pertenecen a ningún subconjunto (es decir, las formas interceptadas por el separador en sí) es pequeño.

Cuando existe un separador geométrico, puede usarse para construir algoritmos de divide y vencerás para resolver varios problemas en geometría computacional.

Separadores de formas cerradas

Un caso simple en el que se garantiza que existe un separador es el siguiente::[1]​[2]​

Dado un conjunto de n cuadrados paralelos de ejes disjuntos en el plano, hay un rectángulo R tal que, como máximo, 2n / 3 de los cuadrados están dentro de R, como máximo 2n / 3 de los cuadrados están fuera de R, y como máximo O (sqrt (n)) de los cuadrados no están dentro ni fuera de R (es decir, intersecan el límite de R).

Por lo tanto, R es un separador geométrico que separa los n cuadrados en dos subconjuntos ("dentro de R" y "fuera de R"), con una "pérdida" relativamente pequeña (los cuadrados intersecados por R se consideran "perdidos" porque no pertenecen a cualquiera de los dos subconjuntos).

Prueba

Defina un rectángulo grosor 2 como un rectángulo de eje paralelo con una relación de aspecto de como máximo 2.

Supongamos que R₀ es un rectángulo de 2 grasas de área mínima que contiene los centros de al menos n / 3 cuadrados. Por lo tanto, cada rectángulo de 2 grasas más pequeño que R₀ contiene menos de n / 3 cuadrados.

Por cada t en [0,1), deje que R_t sea un rectángulo de grosor 2 con el mismo centro que R_0, inflado por 1 + t.

• R_t contiene R₀, por lo que contiene los centros de al menos n/3 cuadrados.
• Rt Es menos de dos veces tan grande como R0, así que pueda ser cubierto por dos 2-rectángulos gordos que es más pequeño que R0. Cada cual de estos 2-los rectángulos gordos contiene los centros de menos de n/3 plazas. Por lo tanto Rt contiene los centros de menos de 2n/3 plazas.

Ahora queda por demostrar que hay una t para la cual R _{t se} cruza en la mayoría de los cuadrados O (sqrt ( n )).

Primero, considere todos los "cuadrados grandes" - los cuadrados cuya longitud lateral es al menos . Para cada t , el perímetro de R _t es como máximo 2 · perímetro ( R ₀ ) que es como máximo 6 · ancho ( R ₀ ), por lo que puede intersecarse como máximo cuadrados grandes

A continuación, considere todos los "cuadrados pequeños": los cuadrados cuya longitud lateral es menor que .

Para cada t , defina: intersect ( t ) como el conjunto de pequeños cuadrados intersectados por el límite de R _t . Para cada t ₁ y t ₂ , si, luego . Por lo tanto, hay una brecha de al menosentre el límite de R _{t 1} y el límite de R _{t 2} . Por lo tanto, la intersección ( t ₁ ) y la intersección ( t ₂ ) son disjuntas. Por lo tanto:

${\displaystyle \sum _{j=0}^{{\sqrt {n}}-1}{|\operatorname {intersect} (j/{\sqrt {n}})|}\leq n}$

Por tanto por el principio de casillero allí es un seguro j0 para qué:

${\displaystyle |\operatorname {intersect} (j_{0}/{\sqrt {n}})|\leq {\sqrt {n}}}$

El separator buscamos es el rectángulo Rt, dónde .${\displaystyle t=j_{0}/{\sqrt {n}}}$[3]​

Ejemplo de aplicación

Usando este teorema del separador, podemos resolver ciertos problemas en geometría computacional de la siguiente manera:

• Separe el conjunto de cuadrados de entrada en dos subconjuntos disjuntos;
• Resuelva el problema en cada subconjunto por separado;
• Combine las soluciones a los dos subproblemas y obtenga una solución aproximada al problema original.

Generalizaciones

El teorema anterior se puede generalizar de muchas maneras diferentes, posiblemente con constantes diferentes. Por ejemplo:

• En lugar de cuadrados, la colección de entrada puede contener objetos gruesos arbitrarios , como: círculos, rectángulos con una relación de aspecto acotada, etc.
• En lugar de formas bidimensionales en un plano, la colección de entrada puede contener objetos de cualquier dimensión y pueden ubicarse en un toro d- dimensional .[1] El teorema anterior se puede generalizar de muchas maneras diferentes, posiblemente con constantes diferentes.
• En lugar de exigir que las formas en la colección de entrada sean disjuntas, podemos establecer un requisito más débil, que la colección es:[1]​
  • k-grueso , es decir, cada punto está cubierto por k formas diferentes como máximo .
  • Espesor de lk , es decir, cada punto está cubierto por un máximo de k formas diferentes con una relación de tamaño (tamaño de la forma más grande dividido por el tamaño de la forma más pequeña) como máximo l .
  • k-sobrecargado , es decir, para cualquier subcolección de formas, la suma de sus medidas individuales es como máximo k veces la medida de su unión..
    • En lugar de un separador rectangular, el separador puede tener cualquier forma que pueda cubrirse con copias más pequeñas de sí mismo.
    • En lugar de limitar el número de formas en cada lado del separador, es posible vincular cualquier medida que satisfaga ciertos axiomas.[2]​

Optimidad

La proporción de 1: 2, en el teorema del separador cuadrado anterior, es la mejor que se puede garantizar: hay colecciones de formas que no se pueden separar en una mejor proporción utilizando un separador que cruza solo formas O (sqrt ( n )). Aquí hay una de esas colecciones (del teorema 34 de ):[1]​

Considere un triángulo equilátero . En cada uno de sus 3 vértices, coloque N / 3 formas dispuestas en una espiral exponencial, de modo que el diámetro aumente en un factor constante cada vuelta de la espiral, y cada forma toque a sus vecinas en el orden en espiral. Por ejemplo, comience con un rectángulo de 1 por,, donde Φ es la proporción áurea . Agregue un cuadrado adyacente by por Φ y obtenga otro rectángulo dorado. Agregue un cuadrado adyacente (1 + Φ) -por- (1 + Φ) y obtenga un rectángulo dorado más grande, y así sucesivamente.

Ahora, para separar más de 1/3 de las formas, el separador debe separar las formas O ( N ) de dos vértices diferentes. Pero para hacer esto, el separador debe intersecar las formas O ( N ).

Separadores hiperplanos

Dado un conjunto de N = 4 k rectángulos paralelos paralelos disjuntos en el plano, hay una línea, ya sea horizontal o vertical, de tal manera que al menos N / 4 rectángulos se encuentran completamente a cada lado del mismo (por lo tanto, como máximo N / 2 rectángulos están intersectados por la línea de separación).

Prueba

Defina W como la línea vertical más occidental con al menos N / 4 rectángulos enteramente a su oeste. Hay dos casos:

• Si hay al menos N / 4 rectángulos completamente al este de W , entonces W es un separador vertical.
• De lo contrario, al mover W ligeramente hacia el oeste, obtenemos una línea vertical que interseca más de N / 2 rectángulos. Encuentre un punto en esta línea que tenga al menos N / 4 rectángulos arriba y N / 4 rectángulos debajo, y dibuje un separador horizontal a través de él.

Optimidad

El número de formas intersectadas, garantizado por el teorema anterior, es O ( N ). Este límite superior es asintóticamente apretado incluso cuando las formas son cuadradas, como se ilustra en la figura de la derecha. Esto está en marcado contraste con el límite superior de las formas intersectadas O ( √ N ), lo que se garantiza cuando el separador es una forma cerrada (consulte la sección anterior ).

Además, cuando las formas son rectángulos arbitrarios, hay casos en los que ninguna línea que separe más de un rectángulo puede cruzar menos de N / 4 rectángulos, como se ilustra en la figura a la derecha.[4]​

Generalizaciones

El encima el teorema puede ser generalizado de rectángulos disjuntos a k-rectángulos gruesos. Además, por inducción en d, es posible de generalizar el encima teorema a d dimensiones y conseguir el teorema siguiente:[1]​

Dado N axial-paralelo d-cajas cuyos interiores son k-gruesos, allí existe un axial-paralelo hyperplane tal que al menos:

${\displaystyle \lfloor (N+1-k)/(2d)\rfloor }$

Del d-mentira de interiores de las cajas a cada lado del hyperplane.

Para el caso especial cuándo k = N − 1 (i.e. cada punto está contenido en como máximo N − 1 cajas), los controles de teorema siguientes:[1]​

Dadas las d- cajas paralelas al eje N cuyos interiores son gruesos ( N - 1), existe un hiperplano paralelo al eje que separa dos de ellos.

Los objetos no necesitan ser cajas, y los separadores no necesitan ser paralelos a los ejes:

Sea C una colección de posibles orientaciones de hiperplanos (es decir, C = {horizontal, vertical}). Dadas N d -Objetos, de tal manera que cada objeto dos disjuntos están separados por un hiperplano con una orientación de C , cuyos interiores son k de espesor, existe un hiperplano con una orientación de C tal que al menos: ( N + 1 - k ) / O ( C ) de los interiores de los objetos d se encuentran completamente a cada lado del hiperplano.

Versiones algorítmicas

Es posible encontrar los hiperplanos garantizados por los teoremas anteriores en pasos O ( Nd ). Además, si los 2 d listas de los puntos extremos inferior y superior de los intervalos que define el cajas i son pre-ordenados th coordenadas, entonces la mejor tales hiperplano (de acuerdo con una amplia variedad de medidas de optimalidad) puede encontrarse en O ( Nd ) pasos.

Separadores que son franjas delimitadas por ancho entre hiperplanos paralelos

Sea Q un conjunto de n puntos en el plano de modo que la distancia mínima entre puntos sea d . Deje a > 0 ser una constante.

Hay un par de líneas paralelas de distancia a , de modo que a lo sumo 2 n / 3 puntos se encuentran a cada lado de la tira, y como máximo los puntos se encuentran dentro de la tira.${\displaystyle 1.3{a \over d}{\sqrt {n}}}$

Equivalente: hay una línea tal que a lo sumo 2 n / 3 puntos se encuentran a cada lado de la misma y a lo sumo.${\displaystyle 1.3{a \over d}{\sqrt {n}}}$ los puntos se encuentran a una distancia de menos de a / 2 de él.

Boceto de prueba

Defina el punto central de Q como un punto o tal que cada línea que lo atraviesa tenga como máximo 2 n / 3 puntos de Q en cada lado. La existencia de un punto central se puede probar utilizando el teorema de Helly .

Para un punto dado p y constante a > 0, defina Pr (a, p, o) como la probabilidad de que una línea aleatoria a través de o se encuentre a una distancia menor que a desde p . La idea es vincular esta probabilidad y así vincular el número esperado de puntos a una distancia menor que a desde una línea aleatoria hasta o . Entonces, según el principio del casillero , al menos una línea a través de o es el separador deseado.

Aplicaciones

Los separadores de ancho limitado se pueden usar para resolver aproximadamente el problema de plegamiento de proteínas.[5]​ También se puede usar para un algoritmo sub-exponencial exacto para encontrar un conjunto independiente máximo , así como varios problemas de cobertura relacionados, en gráficos geométricos.[6]​

Separadores geométricos y separadores de gráficos planos

El teorema del separador plano puede probarse utilizando el teorema del empaque circular para representar un gráfico plano como el gráfico de contacto de un sistema de discos en el plano, y luego encontrando un círculo que forme un separador geométrico para esos discos.

Véase también

• Teorema de emparedado del jamón: dado n objetos medibles en n-espacio dimensional, es posible de dividir todo de ellos por la mitad (con respetar a su medida, i.e. volumen) con un solo (n − 1)-dimensional hyperplane.

Notas

1. Smith, W. D.; Wormald, N. C. (1998). «Geometric separator theorems and applications». Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280). p. 232. ISBN 978-0-8186-9172-0. doi:10.1109/sfcs.1998.743449. 
2. Chan, T. M. (2003). «Polynomial-time approximation schemes for packing and piercing fat objects». Journal of Algorithms 46 (2): 178-189. doi:10.1016/s0196-6774(02)00294-8. 
3. This proof is based on the more general proof of Chan (2003), but with the better constants of Smith&Wormald (1998).
4. MvG (September 2013). «Cutting a cake without destroying the toppings». Math Stack Exchange. Consultado el 13 de enero de 2014. 
5. Miller, Gary L.; Teng, Shang-Hua; Thurston, William; Vavasis, Stephen A. (1997). «Separators for sphere-packings and nearest neighbor graphs». J. ACM 44 (1): 1-29. doi:10.1145/256292.256294. .
6. Fu, B. (2011). «Theory and application of width bounded geometric separators». Journal of Computer and System Sciences 77 (2): 379-392. doi:10.1016/j.jcss.2010.05.003. 

• Datos: Q17016378