separador geométrico

En 1979, Helge Tverberg ^{[ 1 ]} planteó la siguiente pregunta. Para dos enteros positivos k , l , ¿cuál es el número más pequeño n ( k , l ) tal que, para cualquier familia de objetos convexos disjuntos dos a dos en el plano, existe una línea recta que tiene al menos k objetos en un lado y al menos l en el otro lado?

Se conocen los siguientes resultados.

• Obviamente, n (1,1)=1.
• Hope y Katchalski ^{[ 2 ]} demostraron que n ( k ,1) ≤ 12( k -1) para todo k ≥ 2.
• Villanger ^{[ 1 ]} demostró que n(2,2) = ∞: mostró una familia infinita de segmentos disjuntos dos a dos tales que ninguna línea recta tiene dos segmentos en cada lado. Pach y Tardos ^{[ 3 ]} mostraron una construcción más simple usando solo segmentos unitarios, y otra construcción usando solo discos (o cuadrados).

Dado un conjunto de N = 4 k rectángulos disjuntos paralelos a los ejes en el plano, existe una línea, ya sea horizontal o vertical, tal que al menos N / 4 rectángulos se encuentran completamente a cada lado de ella (por lo tanto, como máximo N / 2 rectángulos son intersectados por la línea separadora).

Optimalidad

El número de figuras intersectadas, garantizado por el teorema anterior, es O( N ). Este límite superior es asintóticamente ajustado incluso cuando las figuras son cuadrados, como se ilustra en la figura de la derecha. Esto contrasta notablemente con el límite superior de O( √N ) figuras intersectadas, que se garantiza cuando el separador es una figura cerrada (véase 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 de la derecha. ^{[ 4 ]}

Definimos un rectángulo 2-fat como un rectángulo paralelo a los ejes con una relación de aspecto de como máximo  2.

Sea R ₀ un rectángulo 2-gordo de área mínima que contiene los centros de al menos n /3 cuadrados. Por lo tanto, todo rectángulo 2-gordo menor que R ₀ contiene menos de n /3 cuadrados.

Para cada t en [0,1), sea R _t un rectángulo 2-grueso con el mismo centro que R ₀ , inflado por  1  + t . 

• R _t contiene R ₀ , por lo que contiene los centros de al menos n /3 cuadrados.
• R _t es menor que el doble de R ₀ , por lo que puede ser cubierto por dos rectángulos 2-gruesos que son menores que R ₀ . Cada uno de estos rectángulos 2-gruesos contiene los centros de menos de n /3 cuadrados. Por lo tanto, R _t contiene los centros de menos de 2 n /3 cuadrados.

Ahora queda demostrar que existe un t para el cual R _t interseca como máximo O(sqrt( n )) cuadrados.

Primero, consideremos todos los "cuadrados grandes", los cuadrados cuyo lado tiene una longitud de al menos${\displaystyle \operatorname {width} (R_{0})/2{\sqrt {n}}}$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 intersecar como máximo${\displaystyle 12{\sqrt {n}}}$grandes cuadrados.

A continuación, consideremos todos los "cuadrados pequeños", los cuadrados cuyo lado tiene una longitud menor que${\displaystyle \operatorname {width} (R_{0})/2{\sqrt {n}}}$.

Para cada t , definimos: intersectar( t ) como el conjunto de cuadrados pequeños intersectados por el límite de R _t . Para cada t ₁ y t ₂ , si${\displaystyle |t_{1}-t_{2}|\geq 1/{\sqrt {n}}}$, entonces${\displaystyle |\operatorname {width} (R_{t_{1}})-\operatorname {width} (R_{t_{2}})|\geq \operatorname {width} (R_{0})/{\sqrt {n}}}$Por lo tanto, existe una brecha de al menos${\displaystyle \operatorname {width} (R_{0})/2{\sqrt {n}}}$entre el límite de R _{t 1} y el límite de R _{t 2} . Por lo tanto, intersect( t ₁ ) e intersect( t ₂ ) son disjuntos. Por consiguiente:

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

Por lo tanto, según el principio del palomar, existe un cierto j ₀ para el cual:

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

El separador que buscamos es el rectángulo R _t , donde${\displaystyle t=j_{0}/{\sqrt {n}}}$. ^{[ 7 ]}

Utilizando este teorema del separador, podemos resolver ciertos problemas de 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;
• Combina las soluciones de los dos subproblemas y obtén una solución aproximada al problema original.

El teorema anterior puede generalizarse de muchas maneras diferentes, posiblemente con distintas constantes. 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 limitada, etc.
• En lugar de formas bidimensionales en un plano, la colección de entrada puede contener objetos de cualquier dimensión, y estos pueden estar situados en un toro d -dimensional .
• En lugar de exigir que las formas en la colección de entrada sean disjuntas, podemos poner un requisito más débil, que la colección sea: ^{[ 5 ]}
  • k-grueso , es decir, cada punto está cubierto por como máximo k formas diferentes.
  • lk-grueso , es decir, cada punto está cubierto por como máximo 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, este puede tener cualquier forma que pueda ser cubierta por copias más pequeñas de sí mismo.
• En lugar de limitar el número de figuras en cada lado del separador, es posible limitar cualquier medida que satisfaga ciertos axiomas. ^{[ 6 ]}

La proporción de 1:2, en el teorema del separador cuadrado anterior, es la mejor que se puede garantizar: existen conjuntos de figuras que no se pueden separar en una proporción mejor utilizando un separador que solo cruza O(sqrt( n )) figuras. Aquí hay un ejemplo de dicho conjunto (del teorema 34 de ^{[ 5 ]} ):

Consideremos un triángulo equilátero . En cada uno de sus 3 vértices, coloca N /3 figuras dispuestas en una espiral exponencial, de manera que el diámetro aumente en un factor constante en cada vuelta de la espiral, y cada figura toque a sus vecinas en el orden espiral. Por ejemplo, comienza con un rectángulo de 1 × Φ, donde Φ es la proporción áurea . Agrega un cuadrado adyacente de Φ × Φ y obtendrás otro rectángulo áureo . Agrega un cuadrado adyacente de (1+Φ) × (1+Φ) y obtendrás un rectángulo áureo más grande, y así sucesivamente.

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

Definimos el centro de Q como un punto o tal que cada línea que pasa por él tiene como máximo 2 n /3 puntos de Q en cada lado. La existencia de un centro se puede demostrar utilizando el teorema de Helly .

Para un punto p dado y una constante a > 0, definimos Pr(a, p, o) como la probabilidad de que una línea aleatoria que pasa por o se encuentre a una distancia menor que a de p . La idea es acotar esta probabilidad y, por lo tanto, acotar el número esperado de puntos a una distancia menor que a de una línea aleatoria que pasa por o . Entonces, por el principio del palomar , al menos una línea que pasa por o es el separador deseado.

Los separadores de ancho limitado pueden utilizarse para resolver de forma aproximada el problema del plegamiento de proteínas . ^{[ 9 ]} También pueden utilizarse para un algoritmo subexponencial exacto para encontrar un conjunto independiente máximo , así como varios problemas de cobertura relacionados, en grafos geométricos. ^{[ 8 ]}