Ein intuitiverer Beweis des Zonensatzes?

Der Zonensatz besagt, dass, wenn wir eine Anordnung von n Linien mit einer anderen Linie erstechen, die Gesamtkomplexität ihrer Zone , die Menge aller angrenzenden 0-, 1- und 2-Flächen, O (n) ist. Die tatsächliche Konstante ist ungefähr 6n, zumindest wie in verschiedenen Lehrbüchern angegeben, und der Beweis erfolgt durch Induktion mit einem einigermaßen sorgfältigen Ladungsargument.

Diese Frage wurde mir im Unterricht gestellt und ich habe keine Antwort:

Gibt es einen alternativen, intuitiveren Beweis für den Zonensatz?

Jetzt ist mir klar, dass viele Menschen die Induktion sehr intuitiv finden und durch meine Implikation beleidigt wären, und ich bin bereit, das oben Gesagte so zu ändern, dass es für sie lediglich "alterniert". Aber gibt es einen solchen Beweis? Oder sogar ein Beweis aus dem Buch ?

Dies ist nicht sauberer, aber es ist eine gute Vorbereitung für fortgeschrittenere Dinge, und es ist ein gutes Beispiel für Abstraktion ...

Man kann das Davenport-Schinzel-Sequenzargument verwenden. Betrachten Sie die Region über Ihrer Zonenlinie. Jede Linie wird zu einem Strahl, und tatsächlich zu zwei Strahlen, da wir die linke und die rechte Seite als unterschiedlich betrachten. Scannen Sie die Grenze dieser Zone von links nach rechts und notieren Sie, auf welche Strahlen Sie stoßen. Dies ist eine Sequenz, die über 2n Symbole definiert ist, und das Muster abab ist unzulässig. Als solches beträgt die Länge der Sequenz höchstens 2 (2n) -1 = 4n-1. Das Anwenden auf die Zone unterhalb der Linie impliziert eine Grenze der Form 8n.

Es ist nun einfach zu beweisen, dass eine Folge von Symbolen ohne ... a..b..a..b ... als Teilfolge von n Symbolen die Länge 2n-1 hat. Betrachten Sie in der Tat zwei aufeinanderfolgende Erscheinungen desselben Charakters, die in dieser Reihenfolge einander am nächsten sind. Zwischen diesen beiden Zeichen muss jedes angezeigte Zeichen eindeutig sein. Betrachten Sie ein solches Zeichen und beachten Sie, dass wir die verbotene Teilsequenz erhalten, wenn es irgendwo anders in der Zeichenfolge erscheint. Als solches erscheint dieses Zeichen genau einmal in der Zeichenfolge. Entfernen Sie es und entfernen Sie bei Bedarf ein zusätzliches Zeichen, wenn Sie zwei aufeinanderfolgende identische Zeichen erstellt haben. Wenn Sie ein Zeichen aus der Zeichenfolge entfernen, verkürzen Sie es um 2, sodass die maximale Länge der Zeichenfolge 2n-1 beträgt.

Ich finde die Induktion sehr intuitiv und bin beleidigt über Ihre Implikation. Aber welches Anklageargument?

Wlog geht davon aus, dass die Linie, die die Zone definiert, horizontal ist (sonst drehen) und dass sich die Linien in der allgemeinen Position befinden (sonst stören und die Zone komplizierter machen). Entfernen Sie eine der anderen n Linien. Klassifizieren Sie die Kanten der resultierenden Zone als linke oder rechte Grenze, je nachdem, ob sich die Zone rechts oder links befindet. (Einige Kanten sind sowohl linke als auch rechte Grenzen, aber sie werden in der Komplexitätsgrenze zweimal gezählt.) Nach der induktiven Hypothese gibt es höchstens 3n-3 linke Grenzen. (Der Basisfall n = 0 ist trivial.) Durch erneutes Einfügen der gelöschten Zeile werden höchstens 3 linke Grenzen hinzugefügt (eine in der Zeile selbst und zwei beim Teilen älterer linker Grenzen). Somit beträgt die Gesamtzahl der linken Grenzen höchstens 3n. Symmetrisch beträgt die Anzahl der rechten Grenzen höchstens 3n, sodass die Gesamtkomplexität der Zone höchstens 6n beträgt.

Ein Beweis durch ein Ladungsargument wird als Übung (zusammen mit schrittweisen Hinweisen) auf Seite 13 der Handzettel für Berechnungsgeometrieklassen von David Mount gestellt: http://www.cs.umd.edu/class/fall2005/cmsc754/Handouts/ cmsc754-handouts.pdf