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 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,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}$.

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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle (d_1 d_2 < 0) \mbox{ \bf  i } (d_3d_4<0)}
 then return $TRUE$
 6  if Parser nie mógł rozpoznać (błąd składni): {\displaystyle d_1 = 0 \mbox{ \bf  i } }
 NA-ODCINKU$(p_{3},p_{4},p_{1})$ then return $TRUE$
 7  if Parser nie mógł rozpoznać (błąd składni): {\displaystyle d_2 = 0 \mbox{ \bf  i } }
 NA-ODCINKU$(p_{3},p_{4},p_{2})$ then return $TRUE$
 8  if Parser nie mógł rozpoznać (błąd składni): {\displaystyle d_3 = 0 \mbox{ \bf  i } }
 NA-ODCINKU$(p_{1},p_{2},p_{3})$ then return $TRUE$
 9  if Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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}})\leq x_{p_{3}}\leq \max(x_{p_{1}},x_{p_{2}})$
      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 $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|\geq 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.

<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 $Q$, gdzie $|Q|\geq 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:

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 $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\leq 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.