¿Una prueba más intuitiva del teorema de la zona?

El teorema de la zona dice que si apuñalamos una disposición de n líneas con otra línea, la complejidad total de su zona , el conjunto de todas las caras 0, 1 y 2 adyacentes a ella, es O (n). La constante real es algo así como 6n al menos como se indica en varios libros de texto, y la prueba es por inducción con un argumento de carga razonablemente cuidadoso.

Me hicieron esta pregunta en clase y no tengo una respuesta:

¿Existe una prueba alternativa más intuitiva del teorema de la zona?

Ahora me doy cuenta de que muchas personas encuentran la inducción bastante intuitiva y se sentirán ofendidas por mi implicación, y estoy dispuesta a enmendar lo anterior para simplemente "alternarlas". ¿Pero hay alguna prueba? ¿O incluso una prueba del libro ?

Esto no es más limpio, pero es una buena preparación para cosas más avanzadas, y es un buen ejemplo de abstracción ...

Se puede usar el argumento de secuencias Davenport-Schinzel. Considere la región sobre su línea de zona. Cada línea se convierte en un rayo y, de hecho, en dos rayos, ya que consideramos que el lado izquierdo y el derecho son diferentes. Escanee el límite de esta zona de izquierda a derecha, anotando qué rayos encuentra. Esta es una secuencia definida sobre 2n símbolos, y el patrón abab es ilegal. Como tal, la longitud de la secuencia es como máximo 2 (2n) -1 = 4n-1. Aplicarlo a la zona debajo de la línea, implica un límite de la forma 8n.

Ahora, probar que una secuencia de símbolos sin ... a..b..a..b ... como una subsecuencia de n símbolos tiene una longitud 2n-1 es fácil. de hecho, considere dos apariciones consecutivas del mismo personaje más cercanas entre sí en esta secuencia. Claramente, entre estos dos personajes, cada personaje que aparece debe ser único. Considere dicho carácter y observe que si aparece en cualquier otro lugar de la cadena, obtendremos la subsecuencia prohibida. Como tal, este personaje aparece exactamente una vez en la cadena. Elimínelo y elimine un carácter adicional si es necesario si creó dos caracteres idénticos consecutivos. Es decir, eliminar un carácter de la cadena lo acorta en 2, como tal, la longitud máxima de la cadena es 2n-1.

Encuentro la inducción bastante intuitiva y me ofende su implicación. Pero, ¿qué argumento de carga?

Wlog asume que la línea que define la zona es horizontal (de lo contrario, gira) y que las líneas están en posición general (de lo contrario, perturban y complican la zona). Elimina una de las otras n líneas. Clasifique los bordes de la zona resultante como límites izquierdo o derecho, dependiendo de si la zona está a su derecha o izquierda, respectivamente. (Algunos bordes son límites izquierdo y derecho, pero se cuentan dos veces en el límite de complejidad). Según la hipótesis inductiva, hay como máximo 3n-3 límites izquierdos. (El caso base n = 0 es trivial). Reinsertar la línea eliminada agrega como máximo 3 límites izquierdos (uno en la línea misma y dos por dividir los límites izquierdos más antiguos). Por lo tanto, el número total de límites izquierdos es como máximo 3n. Simétricamente, el número de límites correctos es como máximo 3n, por lo que la complejidad total de la zona es como máximo 6n.

Una prueba de un argumento de carga se plantea como un ejercicio (junto con sugerencias paso a paso) en la página 13 de los folletos de la clase de geometría computacional de David Mount: http://www.cs.umd.edu/class/fall2005/cmsc754/Handouts/ cmsc754-handouts.pdf