Zaawansowane algorytmy i struktury danych/Wykład 11

From Studia Informatyczne

Spis treści

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 p będziemy reprezentować jako parę współrzędnych (x_p, y_p) w ustalonym wcześniej kartezjańskim układzie współrzędnych. Dla pary punktów p,q odcinek między nimi będziemy oznaczać przez p-q, a wektor o początku w p i końcu w q przez p\to q. 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 p,q,r będą różnymi punktami o współrzędnych: p=(x_p,y_p), q=(x_q,y_q), i r = (x_r, y_r). Oznaczmy przez \det(p,q,r) wyznacznik definiowany jako:

\det(p,q,r) = \det\left[\begin{matrix} x_p & y_p & 1\\ x_q & y_q & 1\\ x_r & y_r & 1 \end{matrix} \right]

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




Ćwiczenie

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

W celu sprawdzenia, czy współrzędna polarna jest mniejsza, wystarczy sprawdzić, czy punkt p_2 leży po prawej stronie wektora p_0 \to p_1.

Przecinanie się odcinków

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

  • odcinek p_1-p_2 przekracza odcinek p_3-p_4 oraz odcinek p_3-p_4 przekracza odcinek p_1-p_2,
  • koniec jednego z odcinków leży na drugim odcinku.

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

Algorytm sprawdzania, czy odcinki się przecinają


 ODCINKI-SIĘ-PRZECINAJĄ(p_1 - p_2, p_3 - p_4)
 1  d_1 = \det(p_3,p_4, p_1)
 2  d_2 = \det(p_3,p_4, p_2)
 3  d_3 = \det(p_1,p_2, p_3)
 4  d_4 = \det(p_1,p_2, p_4)
 5  if (d_1 d_2 < 0) \mbox{ \bf  i } (d_3d_4<0) then return TRUE
 6  if d_1 = 0 \mbox{ \bf  i } NA-ODCINKU(p_3, p_4, p_1) then return TRUE
 7  if d_2 = 0 \mbox{ \bf  i } NA-ODCINKU(p_3, p_4, p_2) then return TRUE
 8  if d_3 = 0 \mbox{ \bf  i } NA-ODCINKU(p_1, p_2, p_3) then return TRUE
 9  if d_4 = 0 \mbox{ \bf  i } NA-ODCINKU(p_1, p_2, p_4) then return TRUE
 10 return FALSE

Procedura ta używa poniżej zamieszczonej procedury NA-ODCINKU sprawdzającej, czy punkt p_3 współliniowy z odcinkiem p_1 - p_2 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(p_1, p_2, p_3)
 1  if \min(x_{p_1},x_{p_2}) \le x_{p_3} \le \max(x_{p_1},x_{p_2})
      \mbox{ \bf  i } \min(y_{p_1},y_{p_2}) \le y_{p_3} \le \max(y_{p_1},y_{p_2}) then return TRUE
 2  return FALSE

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 d_1 d_2 <0 i d_3 d_4 <0. Warunek d_1 d_2 <0 oznacza, że d_1 i d_2 są niezerowe i mają przeciwne znaki, czyli że jeden z końców p_1 - p_2 leży po lewej stronie p_3-p_4, a drugi po prawej stronie.

Jeżeli któraś z wartości d_1, d_2, d_3, czy d_4 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. x-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 S nazwiemy najmniejszy wypukły wielokąt P zawierający S. Wielokąt ten będziemy oznaczać jako \mathcal{O}(S). W problemie otoczki wypukłej mamy dany zbiór S 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ż \Theta(n \log n) 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 O(f(n)) wynikać będzie algorytm na sortowanie, działający w tym samym czasie O(f(n)+n) = O(f(n)). Skorzystaliśmy tam z faktu, że algorytm sortujący musi co najmniej przeczytać dane wejściowe, co zajmuje czas O(n).

Niech x_1, \ldots, x_n będzie ciągiem n 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 n punktów na płaszczyźnie (x_1, x_1^2), \ldots, (x_n, x_n^2). Punkty te leżą na prawym ramieniu paraboli y = x^2 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 x_1,\ldots,x_n 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 O(n \log n) 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 S, który zawiera kandydatów na wierzchołki otoczki. Każdy punkt z wejściowego zbioru Q 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 S 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 Q, gdzie |Q| \ge 3. Procedura ta używa funkcji:

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

Algorytm Grahama


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

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



Udowodnimy teraz poprawność działania algorytmu Grahama.

Twierdzenie 1

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

Dowód

Dla ciągu punktów (p_0, p_1,\ldots, p_m) otrzymanego w 3 linii algorytmu zdefiniujmy Q_i = \{p_1, \ldots, p_i\} dla i = 2,\ldots, m.

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 Q - Q_m, a więc \mathcal{O}(Q) = \mathcal{O}(Q_m). Wystarczy więc, że pokażemy, że jeżeli algorytm Grahama kończy działanie, to stos S zawiera punkty otoczki wypukłej \mathcal{O}(Q_m).

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

Dla i = 3,\ldots, m, stos S zawiera wierzchołki otoczki \mathcal{O}(Q_{i-1}) w kolejności ich występowania przeciwnej do ruchu wskazówek zegara.


Po wykonaniu linii 6 na stosie znajdują się trzy punkty q_0,q_1,q_2, czyli innymi słowy zbiór Q_2 = Q_{i-1}. Ponieważ zbiór trzyelementowy stanowi swoją własną otoczkę oraz te punkty występują w dobrej kolejności, to niezmiennik zachodzi dla i=3.

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

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


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

\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 P otrzymujemy:

\mathcal{O}(Q_i - P_i) = \mathcal{O}(Q_i),

ale Q_i - P_i = Q_j \cup \{p_i\} i:

\mathcal{O}(Q_j \cup \{p_i\}) = \mathcal{O}(Q_i).

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

Po zakończeniu pętli for mamy i=m+1. Z zachowania niezmiennika wiemy, że na koniec działania algorytmu na stosie S znajduje się otoczka wypukła punktów Q_{i-1} = Q_m. image:End_of_proof.gif

Przeanalizujmy teraz czas działania algorytmu. Jeżeli oznaczymy n = |Q|, to:

  • wybór punktu p_0 możemy zrealizować w czasie O(n),
  • sortowanie punktów w linii 2 możemy wykonać w czasie O(n \log n), 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 O(n), ponieważ ze stosu nie zdejmiemy więcej niż na niego włożyliśmy, czyli n punktów,
  • pętla for w liniach 7-12 wykona się n-3 razy, a więc wykonanie jej wszystkich instrukcji zajmie czas O(n).

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