Otoczka wypukła

01.12.2011 - Michał Karpiński
TrudnośćTrudność

Algorytm Grahama cd.

Otoczkę wypukłą będziemy budowali w kierunku odwrotnym do ruchu wskazówek zegara. Zauważmy, że jeśli weźmiemy gotową otoczkę wypukłą, wyszczególnimy jakikolwiek jej punkt i przejdziemy po całej otoczce w kierunku odwrotnym do ruchu wskazówek zegara, to każde trzy kolejne punkty będą tworzyły tzw. skręt w lewo (patrz rysunek obok). W algorytmie Grahama korzystamy właśnie z tego faktu. Zauważmy też, że skręt w lewo (lub prawo) można łatwo wykryć w czasie stałym korzystając ze znanej już procedury $ NA{-}LEWO $.

Kolejnych kandydatów na otoczkę wypukłą będziemy umieszczali na pomocniczym stosie $ CH $. Po zakończeniu działania algorytmu w $ CH $ będą się znajdowały kolejne punkty otoczki. Ogólną ideę działania algorytmu można opisać w następujący sposób:

1. Pierwsze dwa punkty ze zbioru $ P[1..n] $ umieszczamy na stosie (pamiętamy, że tablica $ P $ jest już posortowana )

2. Układamy kolejne punkty ze zbioru $ P $ na stosie $ CH $ dopóki tworzą - wraz z dwoma elementami na szczycie stosu - skręt w lewo.

3. Jeśli doszliśmy do punktu startowego, algorytm się kończy. W przeciwnym razie napotkaliśmy miejsce, gdzie kolejny punkt z $ P $ wraz z dwoma elementami na szczycie stosu tworzą skręt w prawo. Nazwijmy te punkty kolejno $ A $, $ B $, i $ C $ (patrz rysunek obok; niebieskie krawędzie). $ A $ i $ B $ leżą na stosie, a $ C $ jest kolejnym punktem z $ P $. Widać, że w takim wypadku punkt $ B $ na pewno nie będzie należał do otoczki. Może być kuszące, aby połączyć po prostu punkt $ A $ z $ C $, ale niestety nie jest to poprawne podejście. Mianowicie, może się okazać, że następny element ze stosu (znajdujący się poniżej $ A $) po połączeniu z $ C $ wykluczy $ A $ z bycia częścią otoczki. Może to też być jakiś inny element ze stosu. Co należy zrobić, to usuwać ze stosu kolejne elementy dopóki nie będzie spełniony warunek skrętu w lewo. Przykład "naprawienia własności skrętu w lewo" demonstruje poniższa animacja:

Posiadamy już dostateczną wiedzę, aby zapisać algorytm Grahama w postaci pseudokodu:

Dowód poprawności

Dowodzimy poprawności algorytmu Grahama stosując prostą indukcję przy użyciu następującego niezmiennika pętli zewnętrznej:

Po $ i $-tej iteracji pętli zewnętrznej punkty $ P[1..i] $ są przetworzone tak, że część z nich należy do stosu $ CH $, a część nie. Te z nich, które należą do stosu $ CH $ tworzą kolejno łańcuch krawędzi taki, że dla każdej krawędzi, wszystkie inne punkty nienależące do $ CH $ (a będące w $ P[1..i] $) znajdują się na lewo od niej.

Przed pierwszą iteracją niezmiennik jest zachowany w trywialny sposób. Załóżmy teraz, że jesteśmy po $ i $-tej iteracji i przystępujemy do iteracji $ i+1 $-szej. Zauważmy, że jeśli punkt $ P[i+1] $ psuje własność "skrętu w lewo", to pętla wewnętrzna nam to naprawi. Przy okazji wszystkie punkty, które odrzuci będą znajdowały się na lewo od nowo utworzonej krawędzi. Niezmiennik zostaje zachowany. Gdy pętla się skończy w $ CH $ znajdą się kolejne punkty otoczki wypukłej (na mocy twierdzenia, które udowodniliśmy przy omawianiu algorytmu Jarvisa).

Analiza złożoności

Nie uwzględniając czasu sortowania mogłoby się wydawać, że algorytm Grahama działa w czasie $ O(n^2) $, gdyż zewnętrzna pętla wykonuje się $ n-2 $ razy, a wewnętrzna pętla może przejść po całym stosie $ CH $ (który maksymalnie może zawierać $ n $ elementów). Zauważmy jednak, że każdy punkt ze zbioru $ P $ rozpatrujemy co najwyżej dwa razy - raz gdy zostaje dodany do stosu i raz gdy zostaje usunięty z niego (nie licząc momentów, w których podglądamy wartości dwóch górnych elementów stosu do określenia "skrętu"). Z tego wynika, że właściwa część szukania otoczki wypukłej wykonuje się w czasie $ O(n) $. Jeśli dodamy do tego czas na posortowanie tablicy $ P $, to ogólna złożoność wynosi $ O(n\log n) $.

Przypadki zdegenerowane

Jeśli chodzi o algorytm Grahama, to musimy rozpatrzyć taką samą kwestię, jak przy metodzie pakowania prezentu. Chodzi oczywiście o sytuację, gdy trzy punkty są współliniowe. Problem nietrudno jest rozwiązać dodając odpowiedni warunek do pętli wewnętrznej. Popatrzmy na rysunek. Jeśli punkt $ C $ jest współliniowy z $ B $ i $ A $ (i znajduje się dalej od $ A $), to $ B $ usuwamy, a $ C $ dodajemy do stosu.

Jednak tutaj należy również pamiętać o jednym skrajnym przypadku. Gdy algorytm się skończy może się okazać, że dwa ostatnio dodane punkty do stosu i punkt startowy są współliniowe (warunek w pętli wewnętrznej tego nie wykryje, bo ostatni rozpatrywany punkt to $ P[n] $ – nie porównujemy go z $ P[1] $). Po skończeniu działania pętli zewnętrznej należy porównać punkt $ P[1] $ z dwoma ostatnimi elementami $ CH $ i ostatni element z $ CH $ ewentualnie usunąć.

5
Twoja ocena: Brak Ocena: 5 (5 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com