Zaawansowane algorytmy i struktury danych/Ćwiczenia 11

Zadanie 1

W inkrementalnym problemie otoczki wypukłej chcemy skonstruować algorytm przechowujący zbiór punktów $Q$ i pozwalający na wykonywanie dwóch operacji:

• DODAJ$(p)$ - dodaje punkt $p$ do zbioru $Q$,
• ZAWIERA$(p)$ - sprawdza, czy punkt $p$ leży wewnątrz otoczki wypukłej zbioru $Q$.

Zaproponuj efektywny algorytm dla tego problemu?

Rozwiązanie

Problem ten można rozwiązać tak aby amortyzowany czas wykonania operacji DODAJ wynosił $O(\log n)$. Zauważmy, że można do tego wykorzystać pomysł z algorytmu Grahama, który jest tak na prawdę algorytmem inkrementalnym. Jednak musimy zmienić sposób uporządkowania punktów w otoczce, ponieważ punkt o najmniejszej współrzędnej $y$ może się w trakcie wykonywania algorytmu zmienić. Punkty otoczki możemy przechowywać w dwóch strukturach posortowane po współrzędnej $x$. Wybieramy punkty z otoczki najbardziej na prawo i najbardziej na lewo i one zadają nam podział na te dwie struktury. Wstawianie do tych struktur jest już przeprowadzane w analogiczny sposób do algorytmu Grahama. Mając te dwie struktury sprawdzenie czy wierzchołek leży wewnątrz otoczki jest bardzo proste, np. możemy po prostu sprawdzić, czy otoczka wypukła zbioru $Q$ po dodaniu punktu $p$ by się zmieniła.

Zadanie 2

Niech $w_1,w_2,\dots ,w_n$ będą kolejnymi punktami opisującymi wierzchołki zamkniętego wielokąta $W$. Zaproponuj efektywny algorytm sprawdzania, czy dany punkt $p$ leży w jego wnętrzu?

Rozwiązanie

Rozważmy półprostą $l$ poziomą zaczynającą się w punkcie $p$. Zauważ, że półprosta ta przecina nieparzystą liczbę razy boki wielokąta $W$ wtedy i tylko wtedy gdy punkt $p$ leży we wnętrzu wielokąta. Wystarczy więc wyznaczyć liczbę przecięć półprostej $l$ z odcinkami $w_i-w_{imodn+1}$.

Zadanie 3

Pokaż jak w czasie $O(n^2\log n)$ sprawdzić, czy w zbiorze $n$ punktów są trzy punkty współliniowe.

Rozwiązanie

W tym celu wystarczy dla każdego punktu $p$ posortować pozostałe punkty zgodnie z ich współrzędną polarną względem $p$.

Zadanie 4

Triangulacja zbioru punktów $P$ to podział otoczki wypukłej $P$ na trójkąty w ten sposób, że punkty $P$ są wierzchołkami trójkątów. Zaproponuj algorytm wyznaczania triangulacji zbioru punktów $P$.

Rozwiązanie

Warstwy zbioru $P$ wyznaczamy w sposób indukcyjny. Warstwa pierwsza $Q_1$ to po prostu ${𝒪}(P)$. Dla $i>1$ warstwę $i$-tą definiujemy jako otoczkę wypukłą zbioru punktów $P-\sum _{j=1}^{i-1}{Q}_j$. Zauważ, że każdy zbiór punktów ma co najwyżej $\frac{n}{3}$ niepustych warstw. Można więc je wyznaczyć w całkowitym czasie $O(n^2\log n)$. Dla każdej warstwy $Q_i$ niech $W_i$ będzie wielokątem którego wierzchołki zadane są przez punkty tej warstwy. Mając dwa kolejne wielokąty $W_i$ i $W_{i+1}$ bardzo łatwo możemy wyznaczyć triangulację obszaru znajdującego się miedzy nimi. Po prostu łączymy odcinkami w kolejności ich występowania punkty $W_i$ i $W_{i+1}$ ze sobą tak aby żadne odcinki się nie przecinały. Suma tych triangulacji da w wyniku triangulację zbioru punktów $P$.