Uma prova mais intuitiva do teorema da zona?

O teorema da zona diz que, se apunhalamos um arranjo de n linhas com outra linha, a complexidade total de sua zona , o conjunto de todas as faces 0, 1 e 2 adjacentes a ela é O (n). A constante real é algo como 6n, pelo menos, como declarado em vários livros didáticos, e a prova é por indução com um argumento de cobrança razoavelmente cuidadoso.

Fiz essa pergunta na aula e não tenho resposta:

Existe uma prova alternativa e mais intuitiva do teorema da zona?

Agora percebo que muitas pessoas acham a indução bastante intuitiva e ficariam ofendidas com a minha implicação, e estou disposto a alterar o que foi dito acima para simplesmente "alternar" para elas. Mas existe alguma prova desse tipo? Ou mesmo uma prova do livro ?

Isso não é mais limpo, mas é uma boa preparação para coisas mais avançadas e é um bom exemplo de abstração ...

Pode-se usar o argumento de seqüências de Davenport-Schinzel. Considere a região acima da sua linha de zona. Cada linha se torna um raio, e de fato dois raios, pois consideramos o lado esquerdo e o lado direito como sendo diferentes. Examine o limite desta zona da esquerda para a direita, anotando quais raios você encontra. Esta é uma sequência definida sobre símbolos 2n, e o padrão abab é ilegal. Como tal, o comprimento da sequência é no máximo 2 (2n) -1 = 4n-1. A aplicação na zona abaixo da linha implica um limite do formulário 8n.

Agora, é fácil provar que uma sequência de símbolos sem ... a..b..a..b ... como uma subsequência de n símbolos tem comprimento 2n-1 é fácil. de fato, considere duas aparências consecutivas do mesmo caractere que estão mais próximas uma da outra nesta sequência. Claramente, entre esses dois caracteres, cada caractere que aparece deve ser exclusivo. Considere esse personagem e observe que, se ele aparecer em qualquer outro lugar da string, obteremos a subsequência proibida. Como tal, esse caractere aparece exatamente uma vez na string. Remova-o e remova um caractere extra, se necessário, se você criou dois caracteres idênticos consecutivos. Nomeadamente, a remoção de um caractere da string diminui-o em 2; portanto, o comprimento máximo da string é 2n-1.

Acho a indução bastante intuitiva e estou ofendida por sua implicação. Mas que argumento de cobrança?

O Wlog supõe que a linha que define a zona seja horizontal (mais gire) e que as linhas estejam na posição geral (caso contrário, perturbe e torne a zona mais complicada). Remova uma das outras n linhas. Classifique as arestas da zona resultante como limites esquerdo ou direito, dependendo de a zona estar à direita ou esquerda, respectivamente. (Algumas arestas são limites esquerdo e direito, mas são contadas duas vezes no limite de complexidade.) Pela hipótese indutiva, existem no máximo 3n-3 limites esquerdos. (O caso base n = 0 é trivial.) Reinserir a linha excluída adiciona no máximo 3 limites à esquerda (um na própria linha e dois na divisão dos limites esquerdos mais antigos). Assim, o número total de limites esquerdos é no máximo 3n. Simetricamente, o número de limites direitos é no máximo 3n, portanto, a complexidade total da zona é no máximo 6n.

Uma prova por um argumento de cobrança é apresentada como um exercício (juntamente com dicas passo a passo) na página 13 dos folhetos das classes de geometria computacional de David Mount: http://www.cs.umd.edu/class/fall2005/cmsc754/Handouts/ cmsc754-handouts.pdf