discrepancia geométrica

La teoría de la discrepancia geométrica ^{[ 1 ]} es un subcampo de la teoría de la discrepancia que se ocupa del equilibrio de conjuntos geométricos, como intervalos o rectángulos . La pregunta general de investigación en este campo es: dado un conjunto de puntos en un espacio geométrico y un conjunto de objetos en el mismo espacio, ¿podemos colorear cada punto con uno de dos colores diferentes (por ejemplo, blanco y negro), de manera que cada objeto contenga aproximadamente el mismo número de puntos de cada color?

Formalmente, la discrepancia de un objeto se define como la diferencia entre el número de puntos blancos y el número de puntos negros en ese objeto; el objetivo es colorear los puntos de tal manera que la discrepancia máxima de un objeto sea lo más pequeña posible.

En el caso más simple de discrepancia geométrica, el conjunto de objetos es el conjunto de todos los subintervalos del intervalo real [0,1]. En este caso, es posible obtener una discrepancia de 1: basta con colorear los puntos alternativamente de negro a blanco, de nuevo a negro y de nuevo a blanco. De esta forma, la discrepancia de cada intervalo será 0 o 1.

El problema se vuelve más complejo cuando los puntos no están disponibles con anticipación, sino que llegan uno por uno, y cada punto debe colorearse inmediatamente al llegar. Esta configuración se denomina "Discrepancia de intervalo en línea". Jiang, Kulkarni y Singla demuestran que: ^{[ 2 ] : Sec.3.2}

• Ningún algoritmo en línea puede garantizar una discrepancia constante.
• Colorear aleatoriamente cada punto cuando llega da${\displaystyle {\tilde {O}}({\sqrt {n}})}$discrepancia esperada.
• Si la llegada del punto es adversaria, la discrepancia de cualquier algoritmo en línea es${\displaystyle \Omega ({\sqrt {n}})}$.
• Si la llegada del punto es estocástica, existe un algoritmo eficiente que lo garantiza.${\displaystyle O(n^{c/\log {\log {n}}})}$discrepancia, para alguna constante universal c, con alta probabilidad (es decir, con probabilidad 1-1/poly( n ), donde el exponente del polinomio depende de c ).

Su demostración utiliza una reducción al problema de balanceo de árboles en línea, que es un problema de discrepancia en el que el conjunto de objetos es el conjunto de subárboles de un árbol m -ario completo con altura h . Para este problema, demuestran que, si${\displaystyle h\leq {\log \log n}/C}$para una constante C suficientemente grande y m ≥ 100, entonces existe un algoritmo en línea que alcanza la discrepancia.${\displaystyle O(\log ^{2}n)}$. ^{[ 2 ] : Sec.2}

Tusnady preguntó cuál es la discrepancia cuando el conjunto de objetos es el conjunto de rectángulos paralelos a los ejes contenidos en el cuadrado unitario .

• Beck ^{[ 3 ]} demostró que la discrepancia es al menos Ω(log n ) y como máximo O(log ⁴ n ).
• Nikolov ^{[ 4 ]} demostró que la discrepancia es como máximo O(log ^1.5 n ).

Cuando el conjunto de objetos es el conjunto de todos los rectángulos (posiblemente rotados), entonces:

• Beck ^{[ 3 ]} demostró que la discrepancia es al menos Ω( n ^1/4-ε ) y como máximo O( n ^1/2+ε ) para cualquier ε >0.

Matousek ^{[ 5 ]} estudió la extensión d- dimensional del problema de Tusnady. Mejorando resultados previos de Roth, Schmidt, Beck, Bohus y Srinivasan, demostró una cota superior de${\displaystyle O_{d}((\log n)^{d+1/2}{\sqrt {\log \log n}})}$con una prueba sencilla.

Cuando el conjunto de objetos es el conjunto de semiplanos en el espacio euclidiano d- dimensional:

• Alexander ^{[ 5 ]} demostró una cota inferior de${\displaystyle \Omega (n^{1/2-d/2})}$para cualquier conjunto denso de puntos, es decir, la relación entre las distancias interiores máximas y mínimas está en O( n ^{1/ d} ).
• Matousek ^{[ 6 ]} demostró una cota superior de${\displaystyle C_{d}n^{1/2-d/2}}$. De hecho, este límite superior se cumple no solo para semiplanos sino también para cualquier sistema de conjuntos para el cual la función de ruptura primal esté en O( m ^d ).