Teorema de la zona

En geometría , el teorema de la zona es un resultado que establece la complejidad de la zona de una línea en una disposición de líneas .

Una disposición de líneas , denotada como${\displaystyle A(L)}$es una subdivisión del plano, inducida por un conjunto de líneas${\displaystyle L}$, en células (${\displaystyle 2}$-caras dimensionales), aristas (${\displaystyle 1}$-caras dimensionales) y vértices (${\displaystyle 0}$-caras dimensionales). Dado un conjunto de${\displaystyle n}$pauta${\displaystyle L}$la disposición de las líneas${\displaystyle A(L)}$y una línea${\displaystyle l}$(no pertenece a${\displaystyle L}$), la zona de${\displaystyle l}$es el conjunto de caras intersectadas por${\displaystyle l}$. La complejidad de una zona es el número total de aristas en su límite, expresado como una función de${\displaystyle n}$. El teorema de la zona establece que dicha complejidad es${\displaystyle O(n)}$.

Este resultado se publicó por primera vez en 1985; ^{[ 1 ]} Chazelle et al. dieron el límite superior de${\displaystyle 10n+2}$para la complejidad de la zona de una línea en una disposición. En 1991, ^{[ 2 ]} este límite se mejoró a${\displaystyle \lfloor 9.5n\rfloor -1}$y también se demostró que este es el mejor límite superior posible salvo un pequeño factor aditivo. Luego, en 2011, ^{[ 3 ]} Rom Pinchasi demostró que la complejidad de la zona de una línea en una disposición es como máximo${\displaystyle \lfloor 9.5n\rfloor -3}$y este es un límite ajustado .

Algunos paradigmas utilizados en las diferentes demostraciones del teorema son la inducción , ^{[ 1 ]} la técnica de barrido , ^{[ 2 ] [ 4 ]} la construcción de árboles , ^{[ 5 ]} y las secuencias de Davenport-Schinzel . ^{[ 6 ] [ 7 ]}

Aunque la versión más popular es para disposiciones de líneas en el plano, existen algunas generalizaciones del teorema de la zona. Por ejemplo, en dimensión${\displaystyle d}$, considerando disposiciones de hiperplanos , la complejidad de la zona de un hiperplano${\displaystyle h}$es el número de facetas (${\displaystyle d-1}$- caras dimensionales) que delimitan el conjunto de celdas (${\displaystyle d}$-caras dimensionales) intersectadas por${\displaystyle h}$. Análogamente, el${\displaystyle d}$El teorema de la zona -dimensional establece que la complejidad de la zona de un hiperplano es${\displaystyle O(n^{d-1})}$. ^{[ 7 ]} Hay considerablemente menos demostraciones para el teorema para dimensión${\displaystyle d\geq 3}$. Para el${\displaystyle 3}$En el caso de -dimensiones, existen demostraciones basadas en técnicas de barrido y para dimensiones superiores se utiliza la relación de Euler: ^{[ 8 ]}$${\displaystyle \sum _{i=0}^{d}(-1)^{i}F_{i}\geq 0.}$$

Otra generalización es considerar arreglos de pseudolíneas (y pseudohiperplanos en dimensión)${\displaystyle d}$) en lugar de líneas (e hiperplanos). Algunas demostraciones del teorema funcionan bien en este caso, ya que no utilizan sustancialmente la rectitud de las líneas en sus argumentos. ^{[ 7 ]}

La principal motivación para estudiar la complejidad de zona en arreglos surge de la búsqueda de algoritmos eficientes para construir arreglos. Un algoritmo clásico es la construcción incremental, que puede describirse a grandes rasgos como la adición de las líneas una tras otra y el almacenamiento de todas las caras generadas por cada una en una estructura de datos apropiada (la estructura habitual para arreglos es la lista de aristas doblemente conectadas (DCEL) ). Aquí, la consecuencia del teorema de zona es que la construcción completa de cualquier arreglo de${\displaystyle n}$Las líneas se pueden hacer a tiempo${\displaystyle O(n^{2})}$, ya que la inserción de cada línea lleva tiempo${\displaystyle O(n)}$.

• Agarwal, PK ; Sharir, M. (2000), "Arrangements and their applications" (PDF) , en Sack, J.-R .; Urrutia, J. (eds.), Handbook of Computational Geometry , Elsevier, pp. 49–119 . .
• Agarwal, PK ; Sharir, M. (2002), "Arreglos de pseudolíneas: dualidad, algoritmos y aplicaciones" , Actas del 13.º Simposio ACM-SIAM sobre Algoritmos Discretos (SODA '02) , San Francisco: Society for Industrial and Applied Mathematics, págs. 800–809 . .
• Aharoni, Y.; Halperin, D .; Hanniel, yo; Har-Peled, S .; Linhart, C. (1999), "Construcción de zonas en línea en disposiciones de líneas en el plano", en Vitter, Jeffrey S .; Zaroliagis, Christos D. (eds.), Ingeniería de algoritmos: tercer taller internacional, WAE'99, Londres, Reino Unido, 19 al 21 de julio de 1999, Actas , Lecture Notes in Computer Science, vol.  1668, Springer-Verlag, págs. 139-153 , CiteSeerX 10.1.1.35.7681 , doi : 10.1007/3-540-48318-7_13 , ISBN   978-3-540-66427-7.
• Bern, MW; Eppstein, D .; Plassman, PE; Yao, FF (1991), "Teoremas del horizonte para líneas y polígonos" (PDF) , en Goodman, JE ; Pollack, R.; Steiger, W. (eds.), Geometría discreta y computacional: Artículos del año especial de DIMACS , DIMACS Ser. Matemáticas discretas y ciencias de la computación teórica, vol.  6, Amer. Math. Soc., pp. 45–66 , MR 1143288  .
• Chazelle, B .; Guibas, LJ ; Lee, DT (1985), "El poder de la dualidad geométrica", BIT Numerical Mathematics , 25 (1): 76–90 , doi : 10.1007/BF01934990 , S2CID 122411548 .
• Edelsbrunner, H. (1987), Algorithms in Combinatorial Geometry , EATCS Monographs in Theoretical Computer Science, Springer-Verlag, ISBN 978-3-540-13722-1.
• Edelsbrunner, H.; O'Rourke , J.; Seidel , R. (1986), "Construcción de arreglos de líneas e hiperplanos con aplicaciones", SIAM Journal on Computing , 15 (2): 341–363 , doi : 10.1137/0215024.
• Edelsbrunner, H.; Guibas , LJ (1989), "Topologically sweeping an arrange", Journal of Computer and System Sciences , 38 (1): 165–194 , doi : 10.1016/0022-0000(89)90038-X.
• Edelsbrunner, H.; Guibas , L.J .; Pach, J .; Pollack, R.; Seidel , R .; Sharir, M. (1992), "Arrangements of curves in the plane—topology, combinatorics, and algorithms", Theoretical Computer Science , 92 (2): 319–336 , doi : 10.1016/0304-3975(92)90319-B.
• Edelsbrunner, H .; Seidel, R.; Sharir, M. (1991), "Sobre el teorema de zona para arreglos de hiperplanos", Nuevos resultados y nuevas tendencias en informática , 555 , Graz, Austria: Springer Science & Business Media: 108, doi : 10.1007/BFb0038185
• Grünbaum, B. (1972), Arrangements and Spreads , Regional Conference Series in Mathematics, vol.  10, Providence, RI: American Mathematical Society.
• Pinchasi, R. (2011), El teorema de la zona revisitado (PDF) (manuscrito inédito)
• Saxena, S. (2021), "Teorema de zona para arreglos en dimensión tres", Information Processing Letters , 172 106161, arXiv : 2006.01428 , doi : 10.1016/j.ipl.2021.106161 , S2CID 219179345