Zaawansowane algorytmy i struktury danych/Wykład 11

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 z 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żącą na niej.

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 $p,q,r$ będą różnymi punktami o współrzędnych: $p=(x_p,y_p)$, $q=(x_q,y_q)$, a $r=(x_r,y_r)$. Oznaczmy przez $\det (p,q,r)$ wyznacznik definiowany jako:

$\det (p,q,r)=\det \left[\begin{array}{ccc}{x}_p& y_p& 1\\ x_q& y_q& 1\\ x_r& y_r& 1\end{array}\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,r$ są 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 $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$.

Przecięcie 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$) 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)and(d_3{d}_4<0)$ then return TRUE
 6  if $d_1=0\text{ i }$ NA-ODCINKU$(p_3,p_4,p_1)$ then return TRUE
 7  if $d_2=0\text{ i }$ NA-ODCINKU$(p_3,p_4,p_2)$ then return TRUE
 8  if $d_3=0\text{ i }$ NA-ODCINKU$(p_1,p_2,p_3)$ then return TRUE
 9  if $d_4=0\text{ 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})\text{ 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ńcy jednego odcina 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ńcy $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 sprawdzenia, 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ą polarna względem tego punktu. Następnie przeglądamy punkty zgodnie z ich uporządkowaniem. Wykorzystamy tą technikę w tym wykładzie 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 ${𝒪}(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ż $\mathrm{\Theta }(n\log n)$ nie istnieje dla tego problemu. Następnie przedstawmy 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))$. Gdzie skorzystaliśmy z faktu, że algorytm sortujący musi co najmniej przeczytać dane wejściowe co zajmuje czas $O(n)$.

Niech $x_1,\dots ,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óżna i dodatnie. Rozważmy teraz $n$ punktów na płaszczyźnie Parser nie mógł rozpoznać (nieznana funkcja „\lots”): {\displaystyle (x_1, x_1^2), \lots, (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,\dots ,x_n$ w ciągu posortowanym.

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,\dots ,p_n)$ będzie tym posortowanym ciągiem,
 3  jeżeli w ciągu $(p_1,\dots ,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,\dots ,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 $n$ 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.

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

<!- Zauważmy, że punkt $p_0$ wybrany w linii 1 algorytmu należy do otoczki, ponieważ nie ma punktu w $Q$ znajdującego się poniżej oraz wszystkie punkty o tej samej współrzędnej $y$ znajdują się na prawo od niego. W linii 2 wszystkie pozostałe punkty w $Q$ sortowane są po ich współrzędnych polarnych względem punktu $p_0$. Jak sprawdzić położenie punktów względem $p_0$ zobacz Ć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 $p_1$ nigdy nie zostanie usunięty ze stosu $S$ jednak ->

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,\dots ,p_m)$ otrzymanego w 3 linii algorytmu zdefiniujmy $Q_i=\{p_1,\dots ,p_i\}$ dla $i=2,\dots ,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 toczki wypukłej. Punkty te to zbiór $Q-Q_m$, a więc ${𝒪}(Q)={𝒪}(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 ${𝒪}(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,\dots ,m$, stos $S$ zawiera wierzchołki otoczki ${𝒪}(Q_{i-1})$ w kierunku ich występowania przeciwnym do ruchu wskazówek zegara.

Po wykonaniu linii 6 na stosie znajdują się trzy wierzchołki $q_0,q_1,q_2$, czyli innymi słowy zbiór $Q_2=Q_{i-1}$. Ponieważ zbiór trzy elementowy stanowi swoją własną otoczkę oraz 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}$. Wierzchołek 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 wierzchołka $p_i$ jest mniejsza niż współrzędna polarna wszystkich wierzchołkó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 ${𝒪}(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 ${𝒪}(Q_j\cup \{p_i\})$ w kolejności przeciwnej do ruchu wskazówek zegara.

Pokażemy teraz, że ${𝒪}(Q_j\cup \{p_i\}$ jest równe ${𝒪}(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}^{\prime }$ 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}^{\prime }\to p_t$. Punkty ${p_t}^{\prime },p_t$ i $p_i$ są posortowane po 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}^{\prime },p_i$ i tym samym nie może należeć do otoczki wypukłej punktów $Q_j\cup \{p_i\}$. 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ą nierówność dla wszystkich punktów w $P$ do zbioru $Q_i$ otrzymujemy:

${𝒪}(Q_i-P_i)={𝒪}(Q_i),$

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

${𝒪}(Q_j\cup \{p_i\})={𝒪}(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$.

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.