Zaawansowane algorytmy i struktury danych/Wykład 11: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 5: Linia 5:
 
== Algorytmy Geometryczne ==
 
== Algorytmy Geometryczne ==
  
Podstawowymi obiektami, jakimi będziemy się tutaj zajmować, są '''punkt''', '''odcinek''', '''wektor''' oraz '''prosta'''. Punkt <math>p</math> będziemy reprezentować jako parę współrzędnych <math>(x_p, y_p)</math> w ustalonym wcześniej kartezjańskim układzie współrzędnych. Dla pary punktów <math>p,q</math> odcinek między nimi będziemy oznaczać przez <math>p-q</math>, a wektor o początku w <math>p</math> i końcu w <math>q</math> przez <math>p\to q</math>. Prostą natomiast będziemy reprezentować przez dowolną parę różnych punktów leżącą na niej.
+
Podstawowymi obiektami, jakimi będziemy się tutaj zajmować, są '''punkt''', '''odcinek''', '''wektor''' oraz '''prosta'''. Punkt <math>p</math> będziemy reprezentować jako parę współrzędnych <math>(x_p, y_p)</math> w ustalonym wcześniej kartezjańskim układzie współrzędnych. Dla pary punktów <math>p,q</math> odcinek między nimi będziemy oznaczać przez <math>p-q</math>, a wektor o początku w <math>p</math> i końcu w <math>q</math> przez <math>p\to q</math>. Prostą natomiast będziemy reprezentować przez dowolną parę różnych punktów leżących na niej.
  
 
=== Względne położenie punktów ===
 
=== Względne położenie punktów ===
  
Atomowymi operacjami używanymi w naszych algorytmach będą operacje wyznaczania względnego położenia trzech punktów. Niech <math>p,q,r</math> będą różnymi punktami o współrzędnych: <math>p=(x_p,y_p)</math>, <math>q=(x_q,y_q)</math>, a <math>r = (x_r, y_r)</math>. Oznaczmy przez <math>\det(p,q,r)</math> wyznacznik definiowany jako:
+
Atomową operacją używaną w naszych algorytmach będzie operacja wyznaczania względnego położenia trzech punktów. Niech <math>p,q,r</math> będą różnymi punktami o współrzędnych: <math>p=(x_p,y_p)</math>, <math>q=(x_q,y_q)</math>, i <math>r = (x_r, y_r)</math>. Oznaczmy przez <math>\det(p,q,r)</math> wyznacznik definiowany jako:
  
 
{{wzor2|1=
 
{{wzor2|1=
Linia 19: Linia 19:
 
}}
 
}}
  
Znak <math>\det(p,q,r)</math> jest równy znakowi sinusa kąta między wektorem <math>p\to r</math> a wektorem <math>p\to q</math>. Powiemy teraz, że punkt <math>r</math> '''leży po lewej''' ('''prawej''') '''stronie''' wektora <math>p \to q</math>, jeżeli <math>\det(p,q,r)>0(</math> (<math>\det(p,q,r)<0</math>). Jeżeli <math>\det(p,q,r)=0</math> to powiemy, że punkty <math>p,q,r</math> są '''współliniowe'''. Wszystkie te sytuacje przedstawione są na poniższej animacji.
+
Znak <math>\det(p,q,r)</math> jest równy znakowi sinusa kąta między wektorem <math>p\to r</math> a wektorem <math>p\to q</math>. Powiemy teraz, że punkt <math>r</math> '''leży po lewej''' ('''prawej''') '''stronie''' wektora <math>p \to q</math>, jeżeli <math>\det(p,q,r)>0</math> (<math>\det(p,q,r)<0</math>). Jeżeli <math>\det(p,q,r)=0</math> to powiemy, że punkty <math>p,q,r</math> są '''współliniowe'''. Wszystkie te sytuacje przedstawione są na poniższej animacji.
  
  
Linia 28: Linia 28:
 
Załóż, że masz dane trzy punkty <math>p_0, p_1, p_2</math>. Czy umiesz sprawdzić, czy współrzędna polarna wektora <math>p_0 \to p_1</math> jest mniejsza niż wektora <math>p_0 \to p_2</math>, tzn. wektor <math>p_0 \to p_1</math> jest przed wektorem <math>p_0 \to p_2</math> w porządku wyznaczonym przez ruch wskazówek zegara wokół punktu <math>p_0</math>?
 
Załóż, że masz dane trzy punkty <math>p_0, p_1, p_2</math>. Czy umiesz sprawdzić, czy współrzędna polarna wektora <math>p_0 \to p_1</math> jest mniejsza niż wektora <math>p_0 \to p_2</math>, tzn. wektor <math>p_0 \to p_1</math> jest przed wektorem <math>p_0 \to p_2</math> w porządku wyznaczonym przez ruch wskazówek zegara wokół punktu <math>p_0</math>?
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
W celu sprawdzenia, czy współrzędna polarna jest mniejsza, wystarczy sprawdzić, czy punkt <math>p_2</math> leży po prawej stronie wektora <math>p_0\to p_1</math>.
+
W celu sprawdzenia, czy współrzędna polarna jest mniejsza, wystarczy sprawdzić, czy punkt <math>p_2</math> leży po prawej stronie wektora <math>p_0 \to p_1</math>.
 
</div>
 
</div>
 
</div>
 
</div>
 
}}
 
}}
  
=== Przecięcie odcinków ===
+
=== Przecinanie się odcinków ===
  
 
Zastanówmy się teraz jak sprawdzić, czy dwa odcinki się przecinają. Powiemy, że odcinek <math>p_1 - p_2</math> ''przekracza'' odcinek <math>p_3 - p_4</math> gdy punkt <math>p_1</math> leży po jednej stronie prostej <math>l</math> przechodzącej przez <math>p_3</math> i <math>p_4</math>, a <math>p_2</math> leży po drugiej stronie prostej <math>l</math>. Odcinek <math>p_1 - p_2</math>
 
Zastanówmy się teraz jak sprawdzić, czy dwa odcinki się przecinają. Powiemy, że odcinek <math>p_1 - p_2</math> ''przekracza'' odcinek <math>p_3 - p_4</math> gdy punkt <math>p_1</math> leży po jednej stronie prostej <math>l</math> przechodzącej przez <math>p_3</math> i <math>p_4</math>, a <math>p_2</math> leży po drugiej stronie prostej <math>l</math>. Odcinek <math>p_1 - p_2</math>
 
przecina <math>p_3 - p_4</math> wtedy, gdy zachodzi co najmniej jeden z warunków:
 
przecina <math>p_3 - p_4</math> wtedy, gdy zachodzi co najmniej jeden z warunków:
* odcinek <math>p_1-p_2</math> przekracza odcinek <math>p_3-p_4</math> oraz
+
* odcinek <math>p_1-p_2</math> przekracza odcinek <math>p_3-p_4</math> oraz odcinek <math>p_3-p_4</math> przekracza odcinek <math>p_1-p_2</math>,
odcinek <math>p_3-p_4</math> przekracza odcinek <math>p_1-p_2</math>,
 
 
* koniec jednego z odcinków leży na drugim odcinku.
 
* koniec jednego z odcinków leży na drugim odcinku.
  
Poniżej zamieszczona procedura ODCINKI-SIĘ-PRZECINAJĄ(<math>p_1 - p_2</math>, <math>p_3 - p_4</math>) zwraca TRUE wtedy i tylko wtedy, gdy jeden z tych warunków zachodzi.
+
Poniżej zamieszczona procedura ODCINKI-SIĘ-PRZECINAJĄ(<math>p_1 - p_2</math>, <math>p_3 - p_4</math>), która zwraca <math>TRUE</math> wtedy i tylko wtedy, gdy jeden z tych warunków zachodzi.
  
 
{{algorytm|sprawdzania, czy odcinki się przecinają|przecinanie_się_odcinków|3=
 
{{algorytm|sprawdzania, czy odcinki się przecinają|przecinanie_się_odcinków|3=
Linia 49: Linia 48:
 
   3  <math>d_3 = \det(p_1,p_2, p_3)</math>
 
   3  <math>d_3 = \det(p_1,p_2, p_3)</math>
 
   4  <math>d_4 = \det(p_1,p_2, p_4)</math>
 
   4  <math>d_4 = \det(p_1,p_2, p_4)</math>
   5  '''if''' <math>(d_1 d_2 < 0) and (d_3d_4<0)</math> '''then''' '''return''' TRUE
+
   5  '''if''' <math>(d_1 d_2 < 0) \mbox{ \bf  i } (d_3d_4<0)</math> '''then''' '''return''' <math>TRUE</math>
   6  '''if''' <math>d_1 = 0 \mbox{ i } </math> [[#współliniowość|NA-ODCINKU]]<math> (p_3, p_4, p_1)</math> '''then''' '''return''' TRUE
+
   6  '''if''' <math>d_1 = 0 \mbox{ \bf  i } </math> [[#współliniowość|NA-ODCINKU]]<math> (p_3, p_4, p_1)</math> '''then''' '''return''' <math>TRUE</math>
   7  '''if''' <math>d_2 = 0 \mbox{ i } </math> [[#współliniowość|NA-ODCINKU]]<math> (p_3, p_4, p_2)</math> '''then''' '''return''' TRUE
+
   7  '''if''' <math>d_2 = 0 \mbox{ \bf  i } </math> [[#współliniowość|NA-ODCINKU]]<math> (p_3, p_4, p_2)</math> '''then''' '''return''' <math>TRUE</math>
   8  '''if''' <math>d_3 = 0 \mbox{ i } </math> [[#współliniowość|NA-ODCINKU]]<math> (p_1, p_2, p_3)</math> '''then''' '''return''' TRUE
+
   8  '''if''' <math>d_3 = 0 \mbox{ \bf  i } </math> [[#współliniowość|NA-ODCINKU]]<math> (p_1, p_2, p_3)</math> '''then''' '''return''' <math>TRUE</math>
   9  '''if''' <math>d_4 = 0 \mbox{ i } </math> [[#współliniowość|NA-ODCINKU]]<math> (p_1, p_2, p_4)</math> '''then''' '''return''' TRUE
+
   9  '''if''' <math>d_4 = 0 \mbox{ \bf  i } </math> [[#współliniowość|NA-ODCINKU]]<math> (p_1, p_2, p_4)</math> '''then''' '''return''' <math>TRUE</math>
   10 '''return''' FALSE
+
   10 '''return''' <math>FALSE</math>
 
}}
 
}}
  
Linia 61: Linia 60:
 
{{algorytm|sprawdza, czy punkt, o którym wiadomo, że jest współliniowy z odcinkiem, leży na tym odcinku|współliniowość|3=
 
{{algorytm|sprawdza, czy punkt, o którym wiadomo, że jest współliniowy z odcinkiem, leży na tym odcinku|współliniowość|3=
 
   NA-ODCINKU<math>(p_1, p_2, p_3)</math>
 
   NA-ODCINKU<math>(p_1, p_2, p_3)</math>
   1  '''if''' <math>\min(x_{p_1},x_{p_2}) \le x_{p_3} \le \max(x_{p_1},x_{p_2}) \mbox{ i } \min(y_{p_1},y_{p_2}) \le y_{p_3} \le \max(y_{p_1},y_{p_2}) </math> '''then''' '''return''' TRUE
+
   1  '''if''' <math>\min(x_{p_1},x_{p_2}) \le x_{p_3} \le \max(x_{p_1},x_{p_2})</math>
   2  '''return''' FALSE
+
      <math>\mbox{ \bf  i } \min(y_{p_1},y_{p_2}) \le y_{p_3} \le \max(y_{p_1},y_{p_2}) </math> '''then''' '''return''' <math>TRUE</math>
 +
   2  '''return''' <math>FALSE</math>
 
}}
 
}}
  
W liniach 1-4 procedury ODCINKI-SIĘ-PRZECINAJĄ wyznaczane są relatywne położenia końców jednego odcinka względem drugiego. Następnie w linii 5 sprawdzane jest, czy odcinki przekraczają się na wzajem, poprzez sprawdzenie, czy <math>d_1 d_2 <0</math> i <math>d_3 d_4 <0</math>. Warunek <math>d_1 d_2 <0</math> oznacza, że <math>d_1</math> i <math>d_2</math> są niezerowe i mają przeciwne znaki, czyli że jeden z końców <math>p_1 - p_2</math> leży po lewej stronie <math>p_3-p_4</math>, a drugi po prawej stronie.
+
W liniach 1-4 procedury [[#przecinanie_się_odcinków|ODCINKI-SIĘ-PRZECINAJĄ]] wyznaczane są relatywne położenia końców jednego odcinka względem drugiego. Następnie w linii 5 sprawdzane jest, czy odcinki przekraczają się na wzajem, poprzez sprawdzenie, czy <math>d_1 d_2 <0</math> i <math>d_3 d_4 <0</math>. Warunek <math>d_1 d_2 <0</math> oznacza, że <math>d_1</math> i <math>d_2</math> są niezerowe i mają przeciwne znaki, czyli że jeden z końców <math>p_1 - p_2</math> leży po lewej stronie <math>p_3-p_4</math>, a drugi po prawej stronie.
  
Jeżeli któraś z wartości <math>d_1, d_2, d_3</math>, czy <math>d_4</math> okaże się zerowa, to oznacza to, że jeden z punktów jest współliniowy z odcinkiem. Aby sprawdzenić, czy odcinki się przecinają, musimy teraz sprawdzić, czy punkt ten leży na tym odcinku. Używamy do tego procedury NA-ODCINKU.
+
Jeżeli któraś z wartości <math>d_1, d_2, d_3</math>, czy <math>d_4</math> okaże się zerowa, to oznacza to, że jeden z punktów jest współliniowy z odcinkiem. Aby sprawdzenić, czy odcinki się przecinają, musimy teraz sprawdzić, czy punkt ten leży na tym odcinku. Używamy do tego procedury [[#współliniowość|NA-ODCINKU]].
  
 
=== Techniki konstrukcji algorytmów ===
 
=== Techniki konstrukcji algorytmów ===
Linia 73: Linia 73:
 
W tym i najbliższym wykładzie przedstawimy trzy ogólne techniki konstrukcji algorytmów geometrycznych. Są to:
 
W tym i najbliższym wykładzie przedstawimy trzy ogólne techniki konstrukcji algorytmów geometrycznych. Są to:
 
* {{kotwica|zamiatanie_polarne|'''zamiatanie polarne'''}} -  Najpierw wybieramy jeden z punktów i porządkujemy resztę obiektów zgodnie z ich współrzędną polarną względem tego punktu. Następnie przeglądamy punkty zgodnie z ich uporządkowaniem. W tym wykładzie wykorzystamy tę technikę do konstrukcji algorytmu znajdującego otoczkę wypukłą zbioru punktów.
 
* {{kotwica|zamiatanie_polarne|'''zamiatanie polarne'''}} -  Najpierw wybieramy jeden z punktów i porządkujemy resztę obiektów zgodnie z ich współrzędną polarną względem tego punktu. Następnie przeglądamy punkty zgodnie z ich uporządkowaniem. W tym wykładzie wykorzystamy tę technikę do konstrukcji algorytmu znajdującego otoczkę wypukłą zbioru punktów.
* {{kotwica|zamiatanie|'''zamiatanie'''}} - W metodzie tej zaczynamy od posortowania obiektów zgodnie z jedną z ich współrzędnych, np. <math>x</math>-ową. Następnie przeglądamy je, przesuwając pionową prostą od lewej do prawej, tak zwaną {{kotwica|miotła|'''miotłę'''}}. W miotle tej pamiętamy informację o obiektach ją przecinających. Metody tej użyjemy w następnym wykładzie do konstrukcji algorytmu sprawdzającego, czy w zbiorze odcinków istnieją dwa odcinki przecinające się ([[../Wykład 11#przecinanie_się_zbioru_odcinków|zobacz]]).
+
* {{kotwica|zamiatanie|'''zamiatanie'''}} - W metodzie tej zaczynamy od posortowania obiektów zgodnie z jedną z ich współrzędnych, np. <math>x</math>-ową. Następnie przeglądamy je, przesuwając pionową prostą od lewej do prawej, tak zwaną {{kotwica|miotła|'''miotłę'''}}. W miotle tej pamiętamy informację o obiektach ją przecinających. Metody tej użyjemy w następnym wykładzie do konstrukcji algorytmu sprawdzającego, czy w zbiorze odcinków istnieją dwa odcinki przecinające się ([[../Wykład 12#przecinanie_sie_zbioru_odcinkow|zobacz]]).
* {{kotwica|dziel_i_zwyciężaj|'''dziel i zwyciężaj'''}} - W konstrukcji algorytmów geometrycznych bardzo przydatna okazuje się także ta metoda. Podział problemu następuje tutaj zazwyczaj względem pewnej pionowej prostej, a następnie wyniki częściowe z dwóch mniejszych problemów są scalane. W ramach następnego wykładu użyjemy tej metody do konstrukcji algorytmu wyznaczającego najmniejszą odległość w zbiorze punktów ([[../Wykład 11#najmniejsza_odległość|zobacz]]).
+
* {{kotwica|dziel_i_zwyciężaj|'''dziel i zwyciężaj'''}} - W konstrukcji algorytmów geometrycznych bardzo przydatna okazuje się także ta metoda. Podział problemu następuje tutaj zazwyczaj względem pewnej pionowej prostej, a następnie wyniki częściowe z dwóch mniejszych problemów są scalane. W ramach następnego wykładu użyjemy tej metody do konstrukcji algorytmu wyznaczającego najmniejszą odległość w zbiorze punktów ([[../Wykład 12#najmniej_odlegla_para|zobacz]]).
  
 
== Otoczka wypukła ==
 
== Otoczka wypukła ==
Linia 84: Linia 84:
 
Zanim przystąpimy do zaprezentowania algorytmu na obliczanie otoczki wypukłej, pokażemy, że w modelu porównaniowym problem ten jest trudniejszy niż problem sortowania. Pokażemy transformacje danych wejściowych działającą w czasie liniowym tak, że z algorytmu na znajdowanie otoczki wypukłej w czasie <math>O(f(n))</math> wynikać będzie algorytm na sortowanie, działający w tym samym czasie <math>O(f(n)+n) = O(f(n))</math>. Skorzystaliśmy tam z faktu, że algorytm sortujący musi co najmniej przeczytać dane wejściowe, co zajmuje czas <math>O(n)</math>.
 
Zanim przystąpimy do zaprezentowania algorytmu na obliczanie otoczki wypukłej, pokażemy, że w modelu porównaniowym problem ten jest trudniejszy niż problem sortowania. Pokażemy transformacje danych wejściowych działającą w czasie liniowym tak, że z algorytmu na znajdowanie otoczki wypukłej w czasie <math>O(f(n))</math> wynikać będzie algorytm na sortowanie, działający w tym samym czasie <math>O(f(n)+n) = O(f(n))</math>. Skorzystaliśmy tam z faktu, że algorytm sortujący musi co najmniej przeczytać dane wejściowe, co zajmuje czas <math>O(n)</math>.
  
Niech <math>x_1, \ldots, x_n</math> będzie ciągiem <math>n</math> liczb rzeczywistych, który chcemy posortować. Bez straty ogólności załóżmy, że są to liczby parami różne i dodatnie.  Rozważmy teraz <math>n</math> punktów na płaszczyźnie <math>(x_1, x_1^2), \lots, (x_n, x_n^2)</math>. Punkty te leżą na prawym ramieniu paraboli <math>y = x^2</math> w kolejności wzrastania pierwszej współrzędnej. Parabola wyznacza wypukły obszar płaszczyzny, a więc wszystkie te punkty będą występowały na obwodzie otoczki. Co więcej, kolejność ich występowania na otoczce wyznacza kolejność wartości <math>x_1,\ldots,x_n</math> w ciągu posortowanym.
+
Niech <math>x_1, \ldots, x_n</math> będzie ciągiem <math>n</math> liczb rzeczywistych, który chcemy posortować. Bez straty ogólności załóżmy, że są to liczby parami różne i dodatnie.  Rozważmy teraz <math>n</math> punktów na płaszczyźnie <math>(x_1, x_1^2), \ldots, (x_n, x_n^2)</math>. Punkty te leżą na prawym ramieniu paraboli <math>y = x^2</math> w kolejności wzrastania pierwszej współrzędnej. Parabola wyznacza wypukły obszar płaszczyzny, a więc wszystkie te punkty będą występowały na obwodzie otoczki. Co więcej, kolejność ich występowania na otoczce wyznacza kolejność wartości <math>x_1,\ldots,x_n</math> w ciągu posortowanym.
 +
 
 +
Trzeba jednak zaznaczyć, że to rozumowanie jest tylko argumentem za, a nie ścisłym dowodem dolnej granicy dla tego problemu. Zauważmy, że w naszym sprowadzniu wykonujemy operacje podnoszenia do kwadratu, która nie jest dozwolona w modelu porównaniowym. Jednak dowód dolnej kranicy <math>O(n \log n)</math> można także przeprowadzić uwzględniając takie operacje (zobacz: Yao, A. C.-C. "A Lower Bound to Finding Convex Hulls." J. ACM 28, 780-787, 1981.)
  
 
=== Algorytm Grahama ===
 
=== Algorytm Grahama ===
Linia 108: Linia 110:
 
   5  PUSH<math>(p_1,S)</math>
 
   5  PUSH<math>(p_1,S)</math>
 
   6  PUSH<math>(p_2,S)</math>
 
   6  PUSH<math>(p_2,S)</math>
   7  '''for''' <math>i=3</math> '''to''' <math>n</math> '''do'''
+
   7  '''for''' <math>i=3</math> '''to''' <math>m</math> '''do'''
 
   8  '''begin'''
 
   8  '''begin'''
 
   9    '''while''' punkt <math>p_i</math> jest na prawo wektora <math>TOP(S)\to NEXT-TO-TOP(S)</math>  '''do'''
 
   9    '''while''' punkt <math>p_i</math> jest na prawo wektora <math>TOP(S)\to NEXT-TO-TOP(S)</math>  '''do'''
Linia 121: Linia 123:
 
<flash>file=Zasd_ilustr_j.swf|width=600|height=350</flash>
 
<flash>file=Zasd_ilustr_j.swf|width=600|height=350</flash>
  
<!-
+
<!--
 
Zauważmy, że punkt <math>p_0</math> wybrany w linii 1 algorytmu należy do otoczki, ponieważ nie ma punktu w <math>Q</math> znajdującego się poniżej, oraz wszystkie punkty o tej samej współrzędnej <math>y</math> znajdują się na prawo od niego. W linii 2 wszystkie pozostałe punkty w <math>Q</math> sortowane są po ich współrzędnych polarnych względem punktu <math>p_0</math>. Jak sprawdzić położenie punktów względem <math>p_0</math>, zobacz [[#ćwiczenie_współrzędna_polarna|Ćwiczenie powyżej]]. Zauważmy, że jeżeli trzy punkty są współliniowe, to tylko dwa skrajne będą należały do otoczki, a więc  punkty usuwane w linii 3 na pewno nie będą należały do toczki wypukłej.
 
Zauważmy, że punkt <math>p_0</math> wybrany w linii 1 algorytmu należy do otoczki, ponieważ nie ma punktu w <math>Q</math> znajdującego się poniżej, oraz wszystkie punkty o tej samej współrzędnej <math>y</math> znajdują się na prawo od niego. W linii 2 wszystkie pozostałe punkty w <math>Q</math> sortowane są po ich współrzędnych polarnych względem punktu <math>p_0</math>. Jak sprawdzić położenie punktów względem <math>p_0</math>, zobacz [[#ćwiczenie_współrzędna_polarna|Ćwiczenie powyżej]]. Zauważmy, że jeżeli trzy punkty są współliniowe, to tylko dwa skrajne będą należały do otoczki, a więc  punkty usuwane w linii 3 na pewno nie będą należały do toczki wypukłej.
  
 
W liniach 4-6 wstawiane są pierwsze punkty na stos. Punkt <math>p_1</math> nigdy nie zostanie usunięty ze stosu <math>S</math> jednak
 
W liniach 4-6 wstawiane są pierwsze punkty na stos. Punkt <math>p_1</math> nigdy nie zostanie usunięty ze stosu <math>S</math> jednak
->
+
-->
  
 
Udowodnimy teraz poprawność działania algorytmu Grahama.
 
Udowodnimy teraz poprawność działania algorytmu Grahama.
Linia 136: Linia 138:
 
Dla ciągu punktów <math>(p_0, p_1,\ldots, p_m)</math> otrzymanego w 3 linii algorytmu zdefiniujmy <math>Q_i = \{p_1, \ldots, p_i\}</math> dla <math>i = 2,\ldots, m</math>.
 
Dla ciągu punktów <math>(p_0, p_1,\ldots, p_m)</math> otrzymanego w 3 linii algorytmu zdefiniujmy <math>Q_i = \{p_1, \ldots, p_i\}</math> dla <math>i = 2,\ldots, m</math>.
  
Zauważmy, że jeżeli trzy punkty są współliniowe, to tylko dwa skrajne będą należały do otoczki, a więc  punkty usuwane w linii 3 na pewno nie będą należały do toczki wypukłej. Punkty te to zbiór <math>Q - Q_m</math>, a więc <math>\mathcal{O}(Q) = \mathcal{O}(Q_m)</math>. Wystarczy więc, że pokażemy, że jeżeli algorytm Grahama kończy działanie, to stos <math>S</math> zawiera punkty otoczki wypukłej <math>\mathcal{O}(Q_m)</math>.
+
Zauważmy, że jeżeli trzy punkty są współliniowe, to tylko dwa skrajne będą należały do otoczki, a więc  punkty usuwane w linii 3 na pewno nie będą należały do otoczki wypukłej. Punkty te to zbiór <math>Q - Q_m</math>, a więc <math>\mathcal{O}(Q) = \mathcal{O}(Q_m)</math>. Wystarczy więc, że pokażemy, że jeżeli algorytm Grahama kończy działanie, to stos <math>S</math> zawiera punkty otoczki wypukłej <math>\mathcal{O}(Q_m)</math>.
  
 
Udowodnimy to pokazując, że na początku pętli '''for''' w liniach 7-12 zachodzi następujący niezmiennik:
 
Udowodnimy to pokazując, że na początku pętli '''for''' w liniach 7-12 zachodzi następujący niezmiennik:
 
<blockquote>
 
<blockquote>
  Dla <math>i = 3,\ldots, m</math>, stos <math>S</math> zawiera wierzchołki otoczki <math>\mathcal{O}(Q_{i-1})</math> w kierunku ich występowania przeciwnym do ruchu wskazówek zegara.
+
  Dla <math>i = 3,\ldots, m</math>, stos <math>S</math> zawiera wierzchołki otoczki <math>\mathcal{O}(Q_{i-1})</math> w kolejności ich występowania przeciwnej do ruchu wskazówek zegara.
 
</blockquote>
 
</blockquote>
  
  
Po wykonaniu linii 6 na stosie znajdują się trzy wierzchołki <math>q_0,q_1,q_2</math>, czyli innymi słowy zbiór <math>Q_2 = Q_{i-1}</math>. Ponieważ zbiór trzyelementowy stanowi swoją własną otoczkę oraz <font color=red>wierzchołki</font> występują w dobrej kolejności, to niezmiennik zachodzi dla <math>i=3</math>.
+
Po wykonaniu linii 6 na stosie znajdują się trzy punkty <math>q_0,q_1,q_2</math>, czyli innymi słowy zbiór <math>Q_2 = Q_{i-1}</math>. Ponieważ zbiór trzyelementowy stanowi swoją własną otoczkę oraz te punkty występują w dobrej kolejności, to niezmiennik zachodzi dla <math>i=3</math>.
  
Na początku iteracji pętli '''for''' na wierzchołku stosu znajduje się <math>p_{i-1}</math>. Wierzchołek ten został wstawiony na końcu poprzedniej iteracji, gdy <math>i>3</math> bądź w przeciwnym przypadku został wstawiony w linii 7. Niech <math>p_j</math> będzie punktem na wierzchołku <math>S</math> po wykonaniu pętli '''while''' w linii 9-10, ale przed wstawieniem do <math>S</math> punktu <math>p_i</math>. W momencie tym stos zawiera elementy takie same jak przed <math>j+1</math> wykonaniem pętli '''for'''. Z niezmiennika wiemy, że elementy <math>S</math> stanowią otoczkę wypukłą zbioru punktów <math>Q_j</math>. Niech <math>p_k</math> będzie elementem NEXT-TO-TOP<math>(S)</math>.
+
Na początku iteracji pętli '''for''' na wierzchołku stosu znajduje się <math>p_{i-1}</math>. Punkt ten został wstawiony na końcu poprzedniej iteracji, gdy <math>i>3</math> bądź w przeciwnym przypadku został wstawiony w linii 7. Niech <math>p_j</math> będzie punktem na wierzchołku <math>S</math> po wykonaniu pętli '''while''' w linii 9-10, ale przed wstawieniem do <math>S</math> punktu <math>p_i</math>. W momencie tym stos zawiera elementy takie same jak przed <math>j+1</math> wykonaniem pętli '''for'''. Z niezmiennika wiemy, że elementy <math>S</math> stanowią otoczkę wypukłą zbioru punktów <math>Q_j</math>. Niech <math>p_k</math> będzie elementem NEXT-TO-TOP<math>(S)</math>.
  
Ponieważ współrzędna polarna wierzchołka <math>p_i</math> jest mniejsza niż współrzędna polarna wszystkich wierzchołków w <math>Q_j</math>, to będzie on należał do otoczki wypukłej zbioru <math>Q_j \cup \{q_i\}</math>. Co więcej, punkt <math>p_i</math> leży na lewo od wektora <math>p_k\to p_j</math>, w przeciwnym wypadku zdjęlibyśmy <math>p_j</math> ze stosu. Widzimy więc, że wierzchołki <math>\mathcal{O}(Q_j)</math> także będą należeć do otoczki wypukłej zbioru <math>Q_j \cup \{q_i\}</math>. Po wstawieniu <math>p_i</math> do <math>S</math>, stos <math>S</math> zawierał będzie wierzchołki <math>\mathcal{O}(Q_j \cup\{p_i\})</math> w kolejności przeciwnej do ruchu wskazówek zegara.
+
Ponieważ współrzędna polarna punktu <math>p_i</math> jest mniejsza niż współrzędna polarna wszystkich punktów w <math>Q_j</math>, to będzie on należał do otoczki wypukłej zbioru <math>Q_j \cup \{q_i\}</math>. Co więcej, punkt <math>p_i</math> leży na lewo od wektora <math>p_k\to p_j</math>, w przeciwnym wypadku zdjęlibyśmy <math>p_j</math> ze stosu. Widzimy więc, że wierzchołki <math>\mathcal{O}(Q_j)</math> także będą należeć do otoczki wypukłej zbioru <math>Q_j \cup \{q_i\}</math>. Po wstawieniu <math>p_i</math> do <math>S</math>, stos <math>S</math> zawierał będzie wierzchołki <math>\mathcal{O}(Q_j \cup\{p_i\})</math> w kolejności przeciwnej do ruchu wskazówek zegara.
  
  
Linia 154: Linia 156:
  
 
{{wzor2|1=
 
{{wzor2|1=
<math>\mathcal{O}(Q_i - \{p_t\}) = \mathcal{O}(Q_i}   \textrm{ dla każdego } p_t \in P.</math>
+
<math>\mathcal{O}(Q_i - \{p_t\}) = \mathcal{O}(Q_i)   \textrm{ \ \ dla każdego } p_t \in P.</math>
 
}}
 
}}
  
Stosując tę nierówność dla wszystkich punktów w <math>P</math> do zbioru <math>Q_i</math> otrzymujemy:
+
Stosując tą równość dla wszystkich punktów w <math>P</math> otrzymujemy:
  
 
{{wzor2|1=
 
{{wzor2|1=

Wersja z 14:00, 28 wrz 2006

Abstrakt

Wykład ten poświęcimy algorytmom geometrycznym, w których danymi wejściowymi będą zbiory punktów bądź zbiory odcinków na płaszczyźnie. Zaczniemy od przedstawienia podstawowych właściwości odcinków, których będziemy następnie używać w naszych algorytmach. W drugiej części wykładu przedstawimy algorytm Grahama obliczania otoczki wypukłej.

Algorytmy Geometryczne

Podstawowymi obiektami, jakimi będziemy się tutaj zajmować, są punkt, odcinek, wektor oraz prosta. Punkt będziemy reprezentować jako parę współrzędnych w ustalonym wcześniej kartezjańskim układzie współrzędnych. Dla pary punktów odcinek między nimi będziemy oznaczać przez , a wektor o początku w i końcu w przez . Prostą natomiast będziemy reprezentować przez dowolną parę różnych punktów leżących na niej.

Względne położenie punktów

Atomową operacją używaną w naszych algorytmach będzie operacja wyznaczania względnego położenia trzech punktów. Niech będą różnymi punktami o współrzędnych: , , i . Oznaczmy przez wyznacznik definiowany jako:

Znak jest równy znakowi sinusa kąta między wektorem a wektorem . Powiemy teraz, że punkt leży po lewej (prawej) stronie wektora , jeżeli (). Jeżeli to powiemy, że punkty współliniowe. Wszystkie te sytuacje przedstawione są na poniższej animacji.


<flash>file=Zasd_ilustr_I.swf|width=600|height=250</flash>

Ćwiczenie

Załóż, że masz dane trzy punkty . Czy umiesz sprawdzić, czy współrzędna polarna wektora jest mniejsza niż wektora , tzn. wektor jest przed wektorem w porządku wyznaczonym przez ruch wskazówek zegara wokół punktu ?

Przecinanie się odcinków

Zastanówmy się teraz jak sprawdzić, czy dwa odcinki się przecinają. Powiemy, że odcinek przekracza odcinek gdy punkt leży po jednej stronie prostej przechodzącej przez i , a leży po drugiej stronie prostej . Odcinek przecina wtedy, gdy zachodzi co najmniej jeden z warunków:

  • odcinek przekracza odcinek oraz odcinek przekracza odcinek ,
  • koniec jednego z odcinków leży na drugim odcinku.

Poniżej zamieszczona procedura ODCINKI-SIĘ-PRZECINAJĄ(, ), która zwraca wtedy i tylko wtedy, gdy jeden z tych warunków zachodzi.

Algorytm sprawdzania, czy odcinki się przecinają


 ODCINKI-SIĘ-PRZECINAJĄ(, )
 1  
 2  
 3  
 4  
 5  if Parser nie mógł rozpoznać (błąd składni): {\displaystyle (d_1 d_2 < 0) \mbox{ \bf  i } (d_3d_4<0)}
 then return 
 6  if Parser nie mógł rozpoznać (błąd składni): {\displaystyle d_1 = 0 \mbox{ \bf  i } }
 NA-ODCINKU then return 
 7  if Parser nie mógł rozpoznać (błąd składni): {\displaystyle d_2 = 0 \mbox{ \bf  i } }
 NA-ODCINKU then return 
 8  if Parser nie mógł rozpoznać (błąd składni): {\displaystyle d_3 = 0 \mbox{ \bf  i } }
 NA-ODCINKU then return 
 9  if Parser nie mógł rozpoznać (błąd składni): {\displaystyle d_4 = 0 \mbox{ \bf  i } }
 NA-ODCINKU then return 
 10 return 

Procedura ta używa poniżej zamieszczonej procedury NA-ODCINKU sprawdzającej, czy punkt współliniowy z odcinkiem leży na tym odcinku.

Algorytm sprawdza, czy punkt, o którym wiadomo, że jest współliniowy z odcinkiem, leży na tym odcinku


 NA-ODCINKU
 1  if 
      Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{ \bf  i } \min(y_{p_1},y_{p_2}) \le y_{p_3} \le \max(y_{p_1},y_{p_2}) }
 then return 
 2  return 

W liniach 1-4 procedury ODCINKI-SIĘ-PRZECINAJĄ wyznaczane są relatywne położenia końców jednego odcinka względem drugiego. Następnie w linii 5 sprawdzane jest, czy odcinki przekraczają się na wzajem, poprzez sprawdzenie, czy i . Warunek oznacza, że i są niezerowe i mają przeciwne znaki, czyli że jeden z końców leży po lewej stronie , a drugi po prawej stronie.

Jeżeli któraś z wartości , czy okaże się zerowa, to oznacza to, że jeden z punktów jest współliniowy z odcinkiem. Aby sprawdzenić, czy odcinki się przecinają, musimy teraz sprawdzić, czy punkt ten leży na tym odcinku. Używamy do tego procedury NA-ODCINKU.

Techniki konstrukcji algorytmów

W tym i najbliższym wykładzie przedstawimy trzy ogólne techniki konstrukcji algorytmów geometrycznych. Są to:

  • zamiatanie polarne - Najpierw wybieramy jeden z punktów i porządkujemy resztę obiektów zgodnie z ich współrzędną polarną względem tego punktu. Następnie przeglądamy punkty zgodnie z ich uporządkowaniem. W tym wykładzie wykorzystamy tę technikę do konstrukcji algorytmu znajdującego otoczkę wypukłą zbioru punktów.
  • zamiatanie - W metodzie tej zaczynamy od posortowania obiektów zgodnie z jedną z ich współrzędnych, np. -ową. Następnie przeglądamy je, przesuwając pionową prostą od lewej do prawej, tak zwaną miotłę. W miotle tej pamiętamy informację o obiektach ją przecinających. Metody tej użyjemy w następnym wykładzie do konstrukcji algorytmu sprawdzającego, czy w zbiorze odcinków istnieją dwa odcinki przecinające się (zobacz).
  • dziel i zwyciężaj - W konstrukcji algorytmów geometrycznych bardzo przydatna okazuje się także ta metoda. Podział problemu następuje tutaj zazwyczaj względem pewnej pionowej prostej, a następnie wyniki częściowe z dwóch mniejszych problemów są scalane. W ramach następnego wykładu użyjemy tej metody do konstrukcji algorytmu wyznaczającego najmniejszą odległość w zbiorze punktów (zobacz).

Otoczka wypukła

Otoczką wypukłą skończonego zbioru punktów nazwiemy najmniejszy wypukły wielokąt zawierający . Wielokąt ten będziemy oznaczać jako . W problemie otoczki wypukłej mamy dany zbiór i chcemy wyznaczyć wierzchołki otoczki wypukłej w kolejności ich występowania na jej obwodzie. W dalszej części tego wykładu przedstawimy prosty argument pokazujący, że złożoność problemu otoczki wypukłej jest nie mniejsza niż złożoność problemu sortowania. Wydaje się więc, że algorytm działający szybciej niż nie istnieje dla tego problemu. Następnie przedstawimy algorytm osiągający tą złożoność. Będzie to algorytm Grahama, a główny wkład do jego złożoności będzie stanowiło właśnie sortowanie punktów względem ich współrzędnych polarnych.

Trudność problemu

Zanim przystąpimy do zaprezentowania algorytmu na obliczanie otoczki wypukłej, pokażemy, że w modelu porównaniowym problem ten jest trudniejszy niż problem sortowania. Pokażemy transformacje danych wejściowych działającą w czasie liniowym tak, że z algorytmu na znajdowanie otoczki wypukłej w czasie wynikać będzie algorytm na sortowanie, działający w tym samym czasie . Skorzystaliśmy tam z faktu, że algorytm sortujący musi co najmniej przeczytać dane wejściowe, co zajmuje czas .

Niech będzie ciągiem liczb rzeczywistych, który chcemy posortować. Bez straty ogólności załóżmy, że są to liczby parami różne i dodatnie. Rozważmy teraz punktów na płaszczyźnie . Punkty te leżą na prawym ramieniu paraboli w kolejności wzrastania pierwszej współrzędnej. Parabola wyznacza wypukły obszar płaszczyzny, a więc wszystkie te punkty będą występowały na obwodzie otoczki. Co więcej, kolejność ich występowania na otoczce wyznacza kolejność wartości w ciągu posortowanym.

Trzeba jednak zaznaczyć, że to rozumowanie jest tylko argumentem za, a nie ścisłym dowodem dolnej granicy dla tego problemu. Zauważmy, że w naszym sprowadzniu wykonujemy operacje podnoszenia do kwadratu, która nie jest dozwolona w modelu porównaniowym. Jednak dowód dolnej kranicy można także przeprowadzić uwzględniając takie operacje (zobacz: Yao, A. C.-C. "A Lower Bound to Finding Convex Hulls." J. ACM 28, 780-787, 1981.)

Algorytm Grahama

W algorytmie Grahama problem wypukłej otoczki jest rozwiązywany z użyciem stosu , który zawiera kandydatów na wierzchołki otoczki. Każdy punkt z wejściowego zbioru jest raz wkładany na stos, natomiast punkty nie będące wierzchołkami otoczki są ze stosu zdejmowane. W momencie zakończenia działania algorytmu stos zawiera punkty występujące na otoczce w kolejności odwrotnej do ruchu wskazówek zegara.

Danymi wejściowymi do procedury GRAHAM jest zbiór punktów , gdzie . Procedura ta używa funkcji:

  • TOP zwracającej wierzchołek stosu ,
  • NEXT-TO-TOP zwracającej drugi wierzchołek na stosie,
  • POP zdejmującej element znajdujący się na szczycie stosu ze stosu,
  • PUSH wkładającej na szczyt stosu wierzchołek .

Algorytm Grahama


 GRAHAM
 1  niech  będzie punktem z  o najmniejszej współrzędnej , jeżeli
    jest kilka takich punktów, to tym najbardziej na lewo spośród nich,
 2  posortujmy pozostałe punkty z  malejąco po ich współrzędnych polarnych względem ,
    niech  będzie tym posortowanym ciągiem,
 3  jeżeli w ciągu  występują dwa punkty o takiej samej współrzędnej polarnej,
    to pozostaw tylko jeden najbardziej odległy od , niech  będzie
    pozostałym ciągiem punktów,
 4  PUSH
 5  PUSH
 6  PUSH
 7  for  to  do
 8  begin
 9    while punkt  jest na prawo wektora   do
 10    POP
 11 PUSH
 12 end
 13 return 

Działanie tego algorytmu jest przedstawione na animacji poniżej.

<flash>file=Zasd_ilustr_j.swf|width=600|height=350</flash>


Udowodnimy teraz poprawność działania algorytmu Grahama.

Twierdzenie 1

Jeżeli procedura GRAHAM zostanie uruchomiona na zbiorze punktów , gdzie , to kiedy się ona zakończy, stos zawierać będzie elementy otoczki wypukłej w kolejności przeciwnej do ruchu wskazówek zegara.

Dowód

Dla ciągu punktów otrzymanego w 3 linii algorytmu zdefiniujmy dla .

Zauważmy, że jeżeli trzy punkty są współliniowe, to tylko dwa skrajne będą należały do otoczki, a więc punkty usuwane w linii 3 na pewno nie będą należały do otoczki wypukłej. Punkty te to zbiór , a więc . Wystarczy więc, że pokażemy, że jeżeli algorytm Grahama kończy działanie, to stos zawiera punkty otoczki wypukłej .

Udowodnimy to pokazując, że na początku pętli for w liniach 7-12 zachodzi następujący niezmiennik:

Dla , stos zawiera wierzchołki otoczki w kolejności ich występowania przeciwnej do ruchu wskazówek zegara.


Po wykonaniu linii 6 na stosie znajdują się trzy punkty , czyli innymi słowy zbiór . Ponieważ zbiór trzyelementowy stanowi swoją własną otoczkę oraz te punkty występują w dobrej kolejności, to niezmiennik zachodzi dla .

Na początku iteracji pętli for na wierzchołku stosu znajduje się . Punkt ten został wstawiony na końcu poprzedniej iteracji, gdy bądź w przeciwnym przypadku został wstawiony w linii 7. Niech będzie punktem na wierzchołku po wykonaniu pętli while w linii 9-10, ale przed wstawieniem do punktu . W momencie tym stos zawiera elementy takie same jak przed wykonaniem pętli for. Z niezmiennika wiemy, że elementy stanowią otoczkę wypukłą zbioru punktów . Niech będzie elementem NEXT-TO-TOP.

Ponieważ współrzędna polarna punktu jest mniejsza niż współrzędna polarna wszystkich punktów w , to będzie on należał do otoczki wypukłej zbioru . Co więcej, punkt leży na lewo od wektora , w przeciwnym wypadku zdjęlibyśmy ze stosu. Widzimy więc, że wierzchołki także będą należeć do otoczki wypukłej zbioru . Po wstawieniu do , stos zawierał będzie wierzchołki w kolejności przeciwnej do ruchu wskazówek zegara.


Pokażemy teraz, że jest równe . Niech będzie zbiorem punktów zdjętych ze stosu w pętli while w 'tej iteracji pętli for. Rozważmy dowolny punkt oraz niech będzie punktem, który był wtedy poniżej niego na stosie. Ponieważ został zdjęty, to nie jest po lewej stronie wektora . Punkty i są posortowane według współrzędnych polarnych względem punktu , a więc punkt musi należeć do trójkąta o rogach w i tym samym nie może należeć do otoczki wypukłej punktów . Mamy więc:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathcal{O}(Q_i - \{p_t\}) = \mathcal{O}(Q_i) \textrm{ \ \ dla każdego } p_t \in P.}

Stosując tą równość dla wszystkich punktów w otrzymujemy:

ale i:

Tym samym pokazaliśmy, że z zachodzenia niezmiennika w 'tym wykonaniu pętli for dla wynika jego zachodzenie na początku -wszego jej wykonania.

Po zakończeniu pętli for mamy . Z zachowania niezmiennika wiemy, że na koniec działania algorytmu na stosie znajduje się otoczka wypukła punktów . End of proof.gif

Przeanalizujmy teraz czas działania algorytmu. Jeżeli oznaczymy , to:

  • wybór punktu możemy zrealizować w czasie ,
  • sortowanie punktów w linii 2 możemy wykonać w czasie , ponieważ porównanie ich współrzędnych polarnych zajmuje czas stały,
  • zauważmy, że wykonanie pętli while w liniach 9-10 zajmie całkowity czas , ponieważ ze stosu nie zdejmiemy więcej niż na niego włożyliśmy, czyli punktów,
  • pętla for w liniach 7-12 wykona się razy, a więc wykonanie jej wszystkich instrukcji zajmie czas .

Podsumowując, widzimy, że najbardziej kosztownym elementem algorytmu Grahama jest sortowanie wierzchołków, które zajmuje czas i taki też jest czas działania algorytmu.