Otoczka wypukła

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

Inne metody

Do tej pory poznaliśmy dwa algorytmy wyznaczające otoczkę wypukłą na płaszczyźnie i dokładnie je omówiliśmy. Ponadto dokonaliśmy analizy złożoności i udowodniliśmy ich poprawność. Nie musimy się jednak ograniczać tylko do tych dwóch metod. Jak wspomniałem we wstępie, nad problemem otoczki wypukłej pracowało (i dalej pracuje) wielu informatyków.

W ciągu kilkudziesięciu lat powstało mnóstwo różnych algorytmów rozwiązujący ten problem. W tym rozdziale chciałbym przedstawić kilka metod, które pokazują różne podejścia do szukania otoczki. Nie będziemy się wgłębiali zbytnio w te algorytmy. Przedstawiona zostanie tylko ich idea. Zachęcam do przeprowadzenia własnych eksperymentów i badań.

Incremental - metoda przyrostowa

Metoda przyrostowa pokazuje naturalne podejście do rozwiązania problemu otoczki. Wynik będziemy przechowywali na liście podwójnie łączonej (nazwiemy ją oczywiście $ CH $). Idea algorytmu jest taka:

Najpierw dodajemy do $ CH $ dwa pierwsze elementy z $ P $. Następnie iterujemy po zbiorze $ P[3..n] $. Dla każdego punktu $ x $ ze zbioru $ P $ sprawdzamy, czy znajduje się wewnątrz wielokąta wypukłego wyznaczonego przez $ CH $. Jeśli tak: przechodzimy dalej. W przeciwnym wypadku wyznaczamy krawędzie wielokąta $ CH $, które są widoczne z $ x $. Usuwamy te krawędzie i tworzymy nowy wielokąt łącząc $ x $ z dwoma wolnymi wierzchołkami wielokąta $ CH $ (wolne: czyli takie, które mają tylko jednego sąsiada).

Nietrudno zauważyć, że po $ i $-tej iteracji $ CH $ jest otoczką wypukłą dla zboru punktów $ P[1..i] $. Każdy nowy punkt po prostu "doczepiamy" do otoczki. Stąd wzięła się nazwa algorytmu, bo otoczka się tak jakby "rozrasta".

Poprawność dowodzimy przez prostą indukcję, więc szczegóły pominiemy. Niestety ta metoda nie jest zbyt efektywna. Jej złożoność to $ O(n^2) $ z uwagi na to, że dla każdego punktu z $ P $ musimy przejść przez całą listę $ CH $.

Dziel i zwyciężaj

Jeśli znamy algorytm sortowania przez scalanie, to nie będziemy mieli problemu ze zrozumieniem działania algorytmów wyznaczania otoczki wypukłej metodą dziel i zwyciężaj, gdyż w obu przypadkach schemat jest ten sam: rozbijamy problem na dwa pod-problemy, pod-problemy rozwiązujemy rekurencyjnie i rozwiązania pod-problemów scalamy w jedną całość. Ogólną procedurę można by zapisać w taki sposób:

Pozostają pytania: jak dzielić? Jak scalać? Najbardziej intuicyjne byłoby wyznaczenie pionowej prostej dzielącej zbiór $ P $ na dwa równoliczne zbiory. Następnie osobno dla lewej i prawej części wyznaczalibyśmy otoczkę. Gdyby przyjąć taką wersję, to scalenie dwóch otoczek polega na znalezieniu tzw. krawędzi mostowych. Na rysunku obok oznaczone są kolorem żółtym.

Zauważmy, że dzielenie można zrobić w czasie stałym. Wystarczy wcześniej posortować zbiór $ P $ i wybrać element środkowy. Scalanie można zaimplementować tak, że będzie działało w czasie $ O(n) $, ale to zadnie pozostawię czytelnikowi jako ćwiczenie.

Można spróbować innego podejścia. Załóżmy, że nie chcemy sortować zbioru $ P $. W takim wypadku dzielenie jest trywialne: otrzymane podzbiory to po prostu $ P[1..\lfloor \frac{n}{2} \rfloor] $ i $ P[\lceil \frac{n}{2} \rceil ..n] $. Na tych podzbiorach rekurencyjnie szukamy otoczki. Krok scalania będzie jednak bardziej skomplikowany, gdyż otoczki $ CH_1 $ i $ CH_2 $ nie muszą być rozłączne (czyli mogą na siebie zachodzić).

Problem ten można sprytnie rozwiązać: weźmy dowolny punkt leżący wewnątrz otoczki $ CH_1 $ (np. środek ciężkości trójkąta złożonego z trzech dowolnych punktów $ CH_1 $). Oznaczmy ten punkt literą $ p $. Sprawdzamy, czy punkt $ p $ leży wewnątrz otoczki $ CH_2 $. Rozpatrujemy dwa przypadki:

1. Punkt $ p $ leży wewnątrz $ CH_2 $. W takim razie prawdą jest, że $ CH_1 $ jest posortowana kątowo względem punktu $ p $ oraz $ CH_2 $ jest posortowana kątowo względem punktu $ p $. Punkty z $ CH_1 $ i $ CH_2 $ można scalić w czasie liniowym tak jakbyśmy to robili przy sortowaniu przez scalanie. Otrzymujemy nowy zbiór punktów $ CH_1 \cup CH_2 $, który jest posortowany względem $ p $. Znalezienie otoczki dla tego zbioru jest już łatwe: wystarczy użyć algorytmu Grahama. Sortowanie mamy już z głowy więc cały proces będzie miał złożoność $ O(n) $.

2. Punkt $ p $ nie leży wewnątrz $ CH_2 $. Tutaj sprawa się nieznacznie komplikuje, gdyż nie możemy od razu zrobić prostego scalania. Co prawda $ CH_1 $ jest posortowana kątowo względem $ p $, ale $ CH_2 $ (jeszcze) nie. Rozwiązujemy ten problem w następujący sposób: szukamy krawędzie otoczki $ CH_2 $, które są widoczne z punktu $ p $ i je usuwamy (tak jakbyśmy to robili w metodzie przyrostowej). I to wszystko. Teraz wystarczy scalić dwa zbiory i użyć algorytmu Grahama.

Która metoda dzielenia i scalania wydaje się być prostsza? To już zależy od osobistych preferencji. W każdym razie złożoność czasowa i tak się nie zmienia. W obu przypadkach wynosi $ O(n \log n) $.

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com