Zaawansowane algorytmy i struktury danych/Ćwiczenia 11: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
 
Linia 1: Linia 1:
 
== Zadanie 1 ==
 
== Zadanie 1 ==
 
{{kotwica|zadanie 1|}}
 
{{kotwica|zadanie 1|}}
 
+
W '''inkrementalnym problemie otoczki wypukłej''' chcemy skonstruować algorytm przechowujący zbiór punktów <math>Q</math> i pozwalający na wykonywanie dwóch operacji:
 
+
* '''DODAJ'''<math>(p)</math> - dodaje punkt <math>p</math> do zbioru <math>Q</math>,
 
+
* '''ZAWIERA'''<math>(p)</math> - sprawdza, czy punkt <math>p</math> leży wewnątrz otoczki wypukłej zbioru <math>Q</math>.
 +
Zaproponuj efektywny algorytm dla tego problemu?
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie'''  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie'''  
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
 
+
Problem ten można rozwiązać tak aby amortyzowany czas wykonania operacji '''DODAJ''' wynosił <math>O(\log n)</math>. 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 <math>y</math> może się w trakcie wykonywania algorytmu zmienić.  Punkty otoczki możemy przechowywać w dwóch strukturach posortowane po współrzędnej <math>x</math>. 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 <math>Q</math> po dodaniu punktu <math>p</math> by się zmieniła.
</div>
 
 
</div>
 
</div>
 +
</div>
  
 
== Zadanie 2 ==
 
== Zadanie 2 ==
 
{{kotwica|zadanie 2|}}
 
{{kotwica|zadanie 2|}}
 
+
Niech <math>w_1, w_2, \ldots, w_n</math> będą kolejnymi punktami opisującymi wierzchołki zamkniętego wielokąta <math>W</math>. Zaproponuj efektywny algorytm sprawdzania, czy dany punkt <math>p</math> leży w jego wnętrzu?
 
 
  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie'''  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie'''  
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
 
+
Rozważmy półprostą <math>l</math> poziomą zaczynającą się w punkcie <math>p</math>. Zauważ, że półprosta ta przecina nieparzystą liczbę razy boki wielokąta <math>W</math> wtedy i tylko wtedy gdy punkt <math>p</math> leży we wnętrzu wielokąta. Wystarczy więc wyznaczyć liczbę przecięć półprostej <math>l</math> z odcinkami <math>w_{i} - w_{i \mod n + 1}</math>.
</div>
 
 
</div>
 
</div>
 
+
</div>
  
 
== Zadanie 3 ==
 
== Zadanie 3 ==
 
{{kotwica|zadanie 3|}}
 
{{kotwica|zadanie 3|}}
 +
Pokaż jak w czasie <math>O(n^2 \log n)</math> sprawdzić, czy w zbiorze <math>n</math> punktów są trzy punkty współliniowe.
  
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
W tym celu wystarczy dla każdego punktu <math>p</math> posortować pozostałe punkty zgodnie z ich współrzędną polarną względem <math>p</math>.
 +
</div>
 +
</div>
  
 +
== Zadanie 4 ==
 +
{{kotwica|zadanie 4|}}
 +
Triangulacja zbioru punktów <math>P</math> to podział otoczki wypukłej <math>P</math> na trójkąty w ten sposób, że punkty <math>P</math> są wierzchołkami trójkątów. Zaproponuj algorytm wyznaczania triangulacji zbioru punktów <math>P</math>.
  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie'''  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie'''  
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
 
+
Warstwy zbioru <math>P</math> wyznaczamy w sposób indukcyjny. Warstwa pierwsza <math>Q_1</math> to po prostu <math>\mathcal{O}(P)</math>. Dla <math>i>1</math> warstwę <math>i</math>-tą definiujemy jako otoczkę wypukłą zbioru punktów <math>P - \sum_{j=1}^{i-1} Q_j</math>. Zauważ, że każdy zbiór punktów ma co najwyżej <math>\frac{n}{3}</math> niepustych warstw. Można więc je wyznaczyć w całkowitym czasie <math>O(n^2 \log n)</math>. Dla każdej warstwy <math>Q_i</math> niech <math>W_i</math> będzie wielokątem którego wierzchołki zadane są przez punkty tej warstwy. Mając dwa kolejne wielokąty <math>W_i</math> i <math>W_{i+1}</math> bardzo łatwo możemy wyznaczyć triangulację obszaru znajdującego się miedzy nimi. Po prostu łączymy odcinkami w kolejności ich występowania punkty <math>W_i</math> i <math>W_{i+1}</math> ze sobą tak aby żadne odcinki się nie przecinały. Suma tych triangulacji da w wyniku triangulację zbioru punktów <math>P</math>.
 
</div>
 
</div>
 
</div>
 
</div>

Aktualna wersja na dzień 15:40, 30 wrz 2006

Zadanie 1

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

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

Zaproponuj efektywny algorytm dla tego problemu?

Rozwiązanie

Zadanie 2

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

Rozwiązanie

Zadanie 3

Pokaż jak w czasie sprawdzić, czy w zbiorze punktów są trzy punkty współliniowe.

Rozwiązanie

Zadanie 4

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

Rozwiązanie