Zaawansowane algorytmy i struktury danych/Wykład 11

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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.


Ć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  then return 
 6  if  NA-ODCINKU then return 
 7  if  NA-ODCINKU then return 
 8  if  NA-ODCINKU then return 
 9  if  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 
       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.

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:

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.