Une preuve plus intuitive du théorème de zone?

Le théorème de zone dit que si nous poignardons un arrangement de n lignes avec une autre ligne, la complexité totale de sa zone , l'ensemble de toutes les faces 0, 1 et 2 adjacentes, est O (n). La constante réelle est quelque chose comme 6n au moins comme indiqué dans divers manuels, et la preuve est par induction avec un argument de charge raisonnablement prudent.

On m'a posé cette question en classe et je n'ai pas de réponse:

Existe-t-il une preuve alternative et plus intuitive du théorème de zone?

Maintenant, je me rends compte que beaucoup de gens trouvent l'induction assez intuitive et serait offensé par mon implication, et je suis prêt à modifier ce qui précède pour simplement "alterner" pour eux. Mais existe-t-il une telle preuve? Ou même une preuve tirée du livre ?

Ce n'est pas plus propre, mais c'est une bonne préparation pour des choses plus avancées, et c'est un bon exemple d'abstraction ...

On peut utiliser l'argument des séquences de Davenport-Schinzel. Considérez la région au-dessus de votre ligne de zone. Chaque ligne devient un rayon, et en fait deux rayons, car nous considérons que le côté gauche et le côté droit sont différents. Scannez les limites de cette zone de gauche à droite en notant les rayons que vous rencontrez. Il s'agit d'une séquence définie sur 2n symboles, et le motif abab est illégal. Ainsi, la longueur de la séquence est au maximum de 2 (2n) -1 = 4n-1. Son application à la zone en dessous de la ligne implique une limite de la forme 8n.

Maintenant, il est facile de prouver qu'une séquence de symboles sans ... a..b..a..b ... comme sous-séquence de n symboles a une longueur 2n-1. en effet, considérons deux apparitions consécutives du même personnage qui sont les plus proches l'une de l'autre dans cette séquence. Clairement, entre ces deux personnages, chaque personnage qui apparaît doit être unique. Considérez un tel caractère et observez que s'il apparaît ailleurs dans la chaîne, nous obtiendrons la sous-séquence interdite. En tant que tel, ce caractère apparaît exactement une fois dans la chaîne. Supprimez-le et supprimez un caractère supplémentaire si nécessaire si vous avez créé deux caractères identiques consécutifs. À savoir, la suppression d'un caractère de la chaîne le raccourcit de 2, en tant que tel, la longueur maximale de la chaîne est 2n-1.

Je trouve l'induction assez intuitive et je suis offensé par votre implication. Mais quel argument de charge?

Wlog suppose que la ligne définissant la zone est horizontale (sinon tourne) et que les lignes sont en position générale (sinon perturbent et compliquent la zone). Supprimez l'une des n autres lignes. Classifiez les bords de la zone résultante en tant que limites gauche ou droite, selon que la zone se trouve respectivement à droite ou à gauche. (Certaines arêtes sont à la fois des limites gauche et droite, mais elles sont comptées deux fois dans la limite de complexité.) Selon l'hypothèse inductive, il y a au plus 3n-3 limites gauche. (Le cas de base n = 0 est trivial.) La réinsertion de la ligne supprimée ajoute au plus 3 limites de gauche (une sur la ligne elle-même et deux de la division des anciennes limites de gauche). Ainsi, le nombre total de limites gauches est au maximum de 3n. Symétriquement, le nombre de limites droites est au maximum de 3n, donc la complexité totale de la zone est au maximum de 6n.

Une preuve par un argument de charge est présentée comme un exercice (avec des conseils étape par étape) à la page 13 des documents de classe de géométrie computationnelle de David Mount: http://www.cs.umd.edu/class/fall2005/cmsc754/Handouts/ cmsc754-handouts.pdf