Zaawansowane algorytmy i struktury danych/Ćwiczenia 11

From Studia Informatyczne

Spis treści

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, \ldots, 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_{i \mod n + 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 \mathcal{O}(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.