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 intersecadas por el propio separador) es pequeño.
Cuando existe un separador geométrico, se puede usar para construir algoritmos de divide y vencerás para resolver varios problemas en geometría computacional .
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 separados por pares en el plano, existe una línea recta que tiene al menos k objetos en un lado y al menos yo del otro lado?
Dado un conjunto de N = 4 k rectángulos disjuntos paralelos al eje en el plano, hay 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 se cruzan con la línea de separación).
Defina W como la línea vertical más al oeste con al menos N /4 rectángulos completamente al oeste. Hay dos casos:
El número de formas intersecadas, garantizado por el teorema anterior, es O( N ). Este límite superior es asintóticamente estricto incluso cuando las formas son cuadradas, como se ilustra en la figura de la derecha. Esto contrasta marcadamente con el límite superior de las formas intersecadas O( √ N ), que se garantiza cuando el separador es una forma cerrada (consulte la sección anterior ).