Bardziej intuicyjny dowód twierdzenia o strefie?

Twierdzenie o strefie mówi, że jeśli dźgniemy układ n linii inną linią, całkowita złożoność jego strefy , zbiór wszystkich ścian 0, 1 i 2 sąsiadujących z nią, wynosi O (n). Rzeczywista stała to mniej więcej 6n, jak podano w różnych podręcznikach, a dowodem jest indukcja z rozsądnie ostrożnym argumentem ładowania.

Zadano mi to pytanie w klasie i nie mam odpowiedzi:

Czy istnieje alternatywny, bardziej intuicyjny dowód twierdzenia o strefie?

Teraz zdaję sobie sprawę, że wiele osób uważa indukcję za dość intuicyjną i uraziłoby mnie to, co im się wydaje, i jestem gotów zmienić powyższe, aby były dla nich jedynie „alternatywne”. Ale czy jest jakiś taki dowód? A może nawet dowód z książki ?

To nie jest czystsze, ale jest dobrym przygotowaniem do bardziej zaawansowanych rzeczy i jest dobrym przykładem abstrakcji ...

Można użyć argumentu sekwencji Davenporta-Schinzela. Rozważ region nad linią strefy. Każda linia staje się promieniem, a właściwie dwoma promieniami, ponieważ uważamy lewą i prawą stronę za inną. Zeskanuj granicę tej strefy od lewej do prawej, zapisując napotkane promienie. Jest to sekwencja zdefiniowana przez 2n symboli, a abab wzorca jest nielegalny. Jako taka długość sekwencji wynosi co najwyżej 2 (2n) -1 = 4n-1. Nałożenie go na strefę poniżej linii oznacza ograniczenie formularza 8n.

Teraz udowodnienie, że sekwencja symboli bez ... a..b..a..b ... jako podsekwencja n symboli ma długość 2n-1, jest łatwa. Rzeczywiście, rozważ dwa kolejne wystąpienia tego samego znaku, które są najbliżej siebie w tej sekwencji. Oczywiście pomiędzy tymi dwoma znakami każda pojawiająca się postać musi być unikalna. Rozważ taki znak i zauważ, że jeśli pojawi się on gdziekolwiek indziej w ciągu, otrzymamy zabronioną podsekwencję. Jako taki, ten znak pojawia się dokładnie raz w ciągu. Usuń go i w razie potrzeby usuń dodatkowy znak, jeśli utworzyłeś dwa kolejne identyczne znaki. Mianowicie, usunięcie znaku z łańcucha skraca go o 2, dlatego maksymalna długość łańcucha wynosi 2n-1.

Uważam, że indukcja jest dość intuicyjna i obraża mnie twoja implikacja. Ale jaki argument ładowania?

Wlog zakłada, że ​​linia definiująca strefę jest pozioma (w przeciwnym razie obraca się) i że linie są w pozycji ogólnej (w przeciwnym razie zaburzają strefę i komplikują ją). Usuń jedną z pozostałych n linii. Sklasyfikuj krawędzie wynikowej strefy jako lewą lub prawą granicę, w zależności od tego, czy strefa znajduje się odpowiednio po ich prawej czy lewej stronie. (Niektóre krawędzie są zarówno lewą, jak i prawą granicą, ale są liczone dwukrotnie w ramach złożoności.) Zgodnie z hipotezą indukcyjną istnieją co najwyżej 3n-3 lewe granice. (Przypadek podstawowy n = 0 jest trywialny). Ponowne wstawienie usuniętej linii dodaje maksymalnie 3 lewe granice (jedna na samej linii i dwie z podziału starszych lewych granic). Zatem łączna liczba lewych granic wynosi co najwyżej 3n. Symetrycznie liczba prawych granic wynosi co najwyżej 3n, więc całkowita złożoność strefy wynosi co najwyżej 6n.

Dowód argumentu obciążającego stanowi ćwiczenie (wraz ze wskazówkami krok po kroku) na stronie 13 materiałów informacyjnych klasy geometrii Davida Mounta: http://www.cs.umd.edu/class/fall2005/cmsc754/Handouts/ cmsc754-handouts.pdf