1 Geometria obliczeniowa Wykład 10 Dualizacja liniowa c.d. 1. Poziomy 2. Otoczka wypukła Ciągi Davenporta-Schinzela Problemy optymalizacyjne 1. Problem wyważania 2. Problem mediany 3. One-line problem

2 Poziomy. Definicja. Poziomem punktu w układzie prostych U nazywamy liczbę prostych powyżej niego. Algorytm zbuduj podwójnie łączoną listę krawędzi dla układu U i dostatecznie dużej ramki ; for każda k  U do określ poziom lewego punktu przecięcia prostej k z ramką; przejdź po prostej k obliczając odpo- wiednie poziomy analizując kierunki prostych przecinajacych k ; 3 2 11 1 1 2 3 22 3 3 3 2 2 4 4 4 3 3 3 4 00 4

3 Analizując punkt przecięcia danej prostej k z innymi prostymi, obliczamy o ile w tym punkcie zmieni się watość poziomu, tzn. różnicę liczby pro- stych przecinających prostą k od dołu i liczby prostych przecinających k od góry. Lemat. Poziomy dla układu prostych można obliczyć w czasie O(n 2 ). Lemat. Poziomy nie muszą być równoliczne. Liczba wierzchołków poziomów skrajnych układu prostych jest równa rozmiarowi otoczki wypukłej zbioru punktów dualnych do prostych two- rzących układ (o ile nie ma krawędzi pionowych). Dowód. Proste odpowiadające punktom należącym do skrajnych poziomów nie rozdzielają zbioru punktów dualnych do prostych tworzących układ, czyli wierzchołki poziomów skrajnych odpowiadają krawędziom otoczki.

4 Otoczka wypukła. Znalezienie otoczki wypukłej zbioru punktów S jest równoważne znalezieniu górnej i dolnej obwiedni układu prostych dualnych do punktów z S. Algorytm oblicz zbiór prostych dualnych D(S) ; stwórz struktury danych dla obwiedni w postaci zrównoważonych drzew BST ; for każda prosta k  D(S) do wyszukaj punkty przecięcia k z obwiedniami ; aktualizuj struktury danych ;

5 Lemat. Każda prosta układu występuje w górnej (dolnej) obwiedni co najwyżej raz. Dowód. Przecięcie z inną prostą implikuje, że półprosta znajdująca się poniżej (po- wyżej) prostej przecinającej nie należy do obwiedni. Lemat. Otoczkę wypukłą zbioru n punktów na płaszczyźnie możemy wyznaczyć w czasie O(n log n). Dowód. Punkty przecięcia kolejnej dodawanej prostej z dotychczasowymi obwied- niami znajdujemy w czasie O(log n). Aktualizacja struktur danych wymaga czasu O(log n)  (liczba usuwanych krawędzi obwiedni +1). Łączna liczba usuwanych krawędzi nie może przekroczyć liczby krawędzi wstawianych, czyli O(n). Zatem złożoność algorytmu wynosi O(n log n).

6 Ciągi Davenporta-Schinzela. Uogólnijmy nasze rozważania. Definicja. Rozpatrzmy rodzinę I = {f n } funkcji kawałkami ciągłych określonych na R. Krzywą ue(x) = max{f n (x)} nazywamy obwiednią górną, a krzywą le(x) = min{f n (x)} nazywamy obwiednią dolną dla danej rodziny funkcji. Obwiednie możemy znaleźć np. łącząc metodę „dziel i rządź” oraz zamia- tanie. W ten sposób znajdujemy obwiednie dla małych podzbiorów rodziny funkcji I. Obwiednie te są funkcjami kawałami ciągłymi, których kolejne części tworzą fragmenty funkcji z I. Przedziały występowania poszcze- gólnych funkcji wyznaczają podział dziedziny określoności obwiedni. Następnie stosując zamiatanie z każdej pary obwiedni tworzymy jedną.

7 Definicja. Niech U=(u 1, u 2,..., u m ) będzie ciągiem o następujących własnościach: u i  {1, 2,..., n} dla każdego i, u i  u i+1 dla każdego i < m, Nie istnieje podciąg indeksów (i j ) długości s+2 taki, że 1  i 1 < i 2

8 W powyższej definicji elementy ciągu U możemy interpretować jako ko- lejne fragmenty obwiedni tworzonej przez zbiór n funkcji. Jeśli dowolne dwie funkcje przecinają się ze sobą nie więcej niż s razy, to rozmiar takiej obwiedni jest ograniczony przez s (n). Fakt. Zachodzą następujące równości: 1 (n) = n, 2 (n) = O(n), 3 (n) = O(n  (n)), 4 (n) = O(n2  (n) ). Ogólnie: s (n) = O(n  (n) x ), gdzie x = O(  (n) s-3 ) i s > 3, 2s+1 (n) =  (n  (n)), gdzie  (n) jest odwrotnością funkcji Ackermanna. Lemat. Stosując metodę „dziel i rzadź” możemy obliczyć DS(n,s) w czasie O( s (n) log n).

9 Problem wyważania. Dla danej (zorientowanej) prostej k i zbio-ru punktów S, zbiór punktów leżących po lewej (po prawej) stronie prostej k oznacza- my jako SL(k) (odpowiednio SP(k)). Punkty leżące na prostej możemy rozdzielać dowol- nie. Problem. Pragniemy znaleźć prostą k taką, że sumy odległości od k punktów z S leżących po każdej ze stron tej prostej są równe, tzn.  p  SL(k) d(p,k) =  p  SP(k) d(p,k), gdzie d(p,k) oznacza odległość punktu p od prostej k.

10 Ustalmy kierunek prostej k. Zauważmy, że wyraz wolny w równaniu prostej k musi jest średnią wyrazów wolnych prostych równoległych do k i przechodzących przez punkty ze zbioru S. W przestrzeni dualnej proste równoległe odpowiadają punktom o tej samej współ- rzędnej x-owej. Zatem dla każdej wartości x współrzędna y-owa punktu D(k) jest średnią współrzędnych y-owych punktów odpowiadających pozostałym prostym. Średnia z funkcji liniowych jest funkcją liniową, więc zbiór rozwiązań problemu wyważania tworzy w przestrzeni dualnej prostą.

11 Wniosek Wszystkie proste będące rozwiązaniami problemu wyważania przechodzą przez jeden punkt. W ten sposób pokazaliśmy, że rozwiązaniem problemu wyważania jest środek ciężkości zbioru S. Lemat. Rozwiązanie problemu wyważania dla zbioru n punktów na płaszczyźnie można znaleźć w czasie O(n).

12 Problem mediany. Pragniemy znaleźć takie proste, które dzie-lą dany zbiór n punktów na płaszczyźnie S na połowy, tzn. oddzielają  (n+1)/2  punktów z S od reszty. Punkty leżące na prostej rozdzielamy dowolnie. Możemy ten problem sformułować także w następujący sposób: dla danego kierunku znajdź prostą, dla któ- rej osiągane jest : min l-prosta  p  S d(p,l). Fakt. Dla danego kierunku prostej istnieje dokład- nie jedno rozwiązanie, gdy liczba punktów w S jest nieparzysta. Dla parzystej liczby punk- tów rozwiązanie nie musi być jednoznaczne.

13 W przestrzeni dualnej obrazem rozwią- zania są zbiory punktów, które wzdłuż osi y-ów mają powyżej i poniżej tyle sa- mo prostych odpowiadających punktom ze zbioru S, tzn. punkty z  (n+1)/2  -tego poziomu lub znajdujące się między  (n+1)/2  -tym a (  (n-1)/2  )-szym poziomem. Lemat. Zbiór wszystkich median jesteśmy w stanie wyznaczyć w czasie O(n 2 ).

14 One-line problem. Znajdywanie najwęższego pasa, w którym zawiera się dany n-elementowy zbiór S. Problem ten jest znany jako one-line pro- blem - szukanie prostej minimalizującej od- ległość od niej najdalszego punktu S, tzn. szukamy prostych, dla których osiągane jest: min l-prosta max p  S d(p,l). Brzegi pasa musza być styczne do otoczki wypukłej zbioru S (w przeciwnym razie moglibyśmy zmniejszyć szerokość pasa). Definicja. Pary przeciwległych wierzchołków otoczki wypukłej (tzn. punkty styczności pasa) na- zywamy punktami antypodycznymi.

15 Lemat Otoczka wypukła o n wierzchołkach ma n par punktów antypodycznych. Dowód. Obrót pasa o  oznacza, że jego brzegi były styczne do otoczki we wszy- stkich jej punktach. Zmiana punktów styczności oznacza zmianę pary punk- tów antypodycznych. Szerokość pasa jest określona przez iloczyn długości odcinka łączącego punkty antypodyczne i sinus kąta między tym odcinkiem a brzegiem pasa. Wniosek. Pas ma minimalną szerokość, gdy kąt między odcinkiem łączącym punkty antypodyczne a brzegiem pasa jest najmniejszy, tzn. gdy proste wyzna- czające brzegi pasa są w położeniach skrajnych. Zatem jedna z prostych musi zawierać bok otoczki wypukłej.

16 Algorytm znajdź otoczkę wypukłą ; znajdź punkty antypodyczne ; oblicz minimalne szerokości pasów dla każdej pary punktów antypodycznych ; znajdź minimalną szerokość i położenie pasów będących rozwiązaniem problemu; Lemat. One-line problem można rozwiązać w czasie O(n log n) lub w czasie O(n), gdy otoczka wypukła zbioru S. Wniosek. Jeśli otoczka wypukła zbioru S ma n wierzchołków, to istnieje co najwyżej n różnych rozwiązań problemu.

17 Na podstawie wcześniejszych rozważań możemy również stworzyć algorytm roz- wiązujący one-line problem metodą duali- zacji. znajdź układ prostych w prostych w prze- strzeni dulanej odpowiadający zbiorowi S ; oblicz dolną i górną obwiednię ; znajdź odległości wierzchołków obwiedni od przeciwległych krawędzi ; szerokości pasów odpowiadające wyzna- czonym odległościom ; znajdź minimalną szerokość pasa ; Lemat. Stosując dualizację możemy rozwiązać one-line problem w czasie O(n log n).