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 de investigación general 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 modo que cada objeto contenga aproximadamente la misma cantidad 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 manera que la discrepancia máxima de un objeto sea lo más pequeña posible.

Intervalos

En la configuración de discrepancia geométrica más simple, el conjunto de objetos es el conjunto de todos los subintervalos del intervalo real [0,1]. En esta configuración, es posible alcanzar la discrepancia 1: simplemente colorea los puntos alternativamente de negro - blanco - negro - blanco - etc. Entonces, la discrepancia de cada intervalo es 0 o 1.

El problema se vuelve más complicado cuando los puntos no están disponibles de antemano, sino que llegan uno por uno, y cada punto debe colorearse inmediatamente cuando llega. 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 como resultado la discrepancia esperada. ${\displaystyle {\tilde {O}}({\sqrt {n}})}$
• Si el punto de llegada es adversario, 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 garantiza la 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 ). ${\displaystyle O(n^{c/\log {\log {n}}})}$

Su prueba utiliza una reducción al problema de Balanceo de Árboles Online, 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 para una constante suficientemente grande C , y m ≥ 100, entonces existe un algoritmo online que alcanza la discrepancia . ^{[2] : Sec.2} ${\displaystyle h\leq {\log \log n}/C}$ ${\displaystyle O(\log ^{2}n)}$

Rectángulos y cajas

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 los resultados previos de Roth, Schmidt, Beck, Bohus y Srinivasan, demostró un límite superior de con una prueba simple. ${\displaystyle O_{d}((\log n)^{d+1/2}{\sqrt {\log \log n}})}$

Rayas

Cuando el conjunto de objetos es el conjunto de rayas —rectángulos de la forma [a,b]x[0,1] y [0,1]x[a,b]—, la configuración es equivalente al problema de "dos permutaciones": dadas dos permutaciones en un conjunto de n elementos, deberíamos colorear cada elemento de negro o de blanco, de modo que se minimice la discrepancia en cada intervalo de cada permutación (las dos permutaciones son el orden de las coordenadas x y el orden de las coordenadas y de los puntos).

• Spencer demostró que es posible alcanzar una discrepancia de como máximo 2. ^[2]

Jiang, Kulkarni y Singla ^[2] estudian la configuración en línea con llegada de punto estocástico y demuestran que:

• Una coloración aleatoria produce una discrepancia esperada de . ${\displaystyle {\tilde {O}}({\sqrt {n}})}$
• Existe un algoritmo eficiente que garantiza la discrepancia, para una constante universal c, con alta probabilidad . Muestran una aplicación de este resultado a la división justa en línea . ${\displaystyle O(n^{c/\log {\log {n}}})}$

Politopos convexos

Matousek ^[5] y Nikolov ^[4] estudiaron un contexto más general, en el que el conjunto de objetos se induce mediante dilataciones y traslaciones de un politopo convexo fijo . Demostró límites superiores e inferiores para la discrepancia. Los resultados son análogos a los obtenidos para rectángulos y cajas.

Medios espacios

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

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

Referencias

1. Matoušek, Jiří (1999). Discrepancia geométrica: una guía ilustrada . Saltador. ISBN 3-540-65528-X.
2. Jiang, Haotian; Kulkarni, Janardhan; Singla, Sahil (2 de octubre de 2019). "Discrepancia geométrica en línea para llegadas estocásticas con aplicaciones para la minimización de envidia". arXiv : 1910.01073 [cs.DS].
3. Beck, József (1981-12-01). "Dos coloraciones equilibradas de conjuntos finitos en el cuadrado I". Combinatorica . 1 (4): 327–335. doi :10.1007/BF02579453. ISSN  1439-6912.
4. Nikolov, Aleksandar (enero de 2017). "Límites más estrictos para la discrepancia de cajas y politopos". Mathematika . 63 (3): 1091–1113. arXiv : 1701.05532 . doi :10.1112/S0025579317000250. ISSN  0025-5793.
5. Alexander, R. (1990-06-01). "Métodos geométricos en el estudio de irregularidades de distribución". Combinatorica . 10 (2): 115–136. doi :10.1007/BF02123006. ISSN  1439-6912.
6. Matoušek, J. (1995-06-01). "Límites superiores estrictos para la discrepancia de semiespacios". Geometría discreta y computacional . 13 (3): 593–601. doi :10.1007/BF02574066. ISSN  1432-0444.