3. Problem otoczki wypukłej
Definicja 3.1 Niech Q
będzie skończonym zbiorem
punktów na
płaszczyźnie. Najmniejszy zbiór wypukły taki, że każdy
punkt zbioru Q znajduje się albo w jego wnętrzu albo na brzegu,
nazywamy otoczką wypukłą zbioru Q (ang. convex hull).
Otoczkę wypukłą danego zbioru Q oznaczać będziemy przez CH(Q).
W geometrii dowodzi się, że dla
dowolnego zbioru Q na płaszczyźnie,
otoczka wypukła jest wielokątem.
Dokładniej mówi o tym lemat 3.1.
Lemat 3.1 Dla dowolnego n
³3
otoczka wypukła zbioru Q jest wielokątem
wypukłym o
wierzchołkach w pewnych punktach zbioru Q.
Uwaga
Wielokąt jest wypukły wttw, gdy każdy odcinek łączący dwa punkty
wewnętrzne wielokąta leży całkowicie wewnątrz tego wielokąta.
Podstawową własność otoczki wypukłej
danego zbioru punktów, można sformułować następująco:
jeśli dowolną linię leżącą na zewnątrz otoczki, przesunąć w
dowolnym kierunku w stronę otoczki, to musi ona spotkać najpierw jeden
z wierzchołków
otoczki. Otoczka w naturalny sposób definiuje granice danego zbioru
punktów. Wiele problemów geometrycznych wymaga w swoim rozwiązaniu
znalezienia otoczki wypukłej, po to by ułatwić dalsze rozważania.
Przytoczymy tu jako przykład zadanie znalezienia pary najbardziej
odległych punktów w danym zbiorze. Można udowodnić, że punkty te są
wierzchołkami otoczki wypukłej. Zbadanie, które to punkty otoczki,
można
zrealizować w czasie liniowym. Jeśli umiemy rozwiązać szybko problem
otoczki, to będziemy umieli również szybko rozwiązać
problem najbardziej odległych punktów.
|
|
Przykład
3.1 Dla dowolnych trzech punktów nie współliniowych, otoczką
wypukłą jest trójkąt o wierzchołkach w tych punktach. Otoczką
wypukłą czteroelementowego zbioru punktów, w którym żadne trzy nie są
współliniowe, jest czworokątem lub trójkątem. Na rysunku 13.5(a)(b) przedstawiono
przykładowy zbiór punktów i
jego otoczkę wypukłą. J
Problem
Jak znaleźć otoczkę wypukłą danego
zbioru punktów. Na mocy Lematy
3.1, musimy wybrać ze zbioru punktów te, które są wierzchołkami
najmniejszego wielokąta wypukłego otaczającego cały zbiór.
Zastanówmy się, które wierzchołki
zbioru Q na pewno nie mogą być
wierzchołkami otoczki. Jest oczywiste, że jeśli wybraliśmy już jakieś
punkty p i q, to wszystkie punkty leżące na prostej łączącej p z q i
leżące między p i q możemy pominąć. Co więcej, wszystkie punkty leżące
wewnątrz jakiegokolwiek trójkąta utworzonego z punktów zbioru Q,
nie mogą być wierzchołkami otoczki wypukłej. Opierając się na
powyższym kryterium eliminacji punktów, można zaproponować następującą
metodę wyszukiwania zbioru wierzchołków otoczki wypukłej.
Metoda trójkątów
Niech X = Q.
Dla każdej trójki punktów p1, p2, p3
ze
zbioru X,
- jeżeli nie są one współliniowe, to usuń wszystkie punkt zbioru X
leżące wewnątrz trójkąta D(p1,p2,p3),
- jeżeli są współliniowe, to usuń ze zbioru X punkt środkowy (z tej
trójki).
Punkty, które pozostały, tworzą zbiór wierzchołków otoczki
wypukłej zbioru Q, CH(Q).
Poprawność
Po wykonaniu algorytmu, pozostałe w zbiorze X punkty
spełniają warunek:
dowolna trójka punktów p1, p2, p3 ze
zbioru X, tworzy trójkąt, a każdy inny punkt zbioru X znajduje się na
zewnątrz tego trójkąta.
Wynika stąd, że wszystkie punkty
zbioru X muszą należeć do
otoczki wypukłej. Ponadto, z metody konstrukcji zbioru X wynika, że
punkty zbioru Q, które nie należą do zbioru X, znajdują się wewnątrz
pewnego trójkąta utworzonego z punktów zbioru X. Zatem
wielokąt, którego wierzchołkami są punkty zbioru X, jest najmniejszym wypukłym
wielokątem zawierającym wszystkie punkty zbioru Q na brzegu lub wewnątrz.
Przykład 3.2 Na rysunku 13.6 zaznaczono jeden z możliwych trójkątów
utworzonych przez punkty zbioru Q przedstawionego na rysunku 13.5(a). Trzy
punkty znalazły się wewnątrz trójkąta, więc nie będą mogły być wierzchołkami
szukanej otoczki wypukłej. Na rysunku 13.6(b) zaznaczono inny trójkąt, który
pozwala wyeliminować ze zbioru dalsze dwa punkty znajdujące się na brzegu lub
wewnątrz trójkąta. Widać z tego przykładu, że metoda trójkątów może być bardzo
skuteczna, jeśli odpowiednio wybierzemy trójkąty.
|
|
Koszt algorytmu
Jeżeli |Q| = n, to można utworzyć co najwyżej (n nad 3) różnych trójkątów. Wynika
stąd, że pętla zewnętrzna algorytmu wykonuje O(n3)
iteracji. Ponieważ dla każdego trójkąta przeglądamy wszystkie
punkty pozostałe w zbiorze X, zatem pętla wewnętrzna wykonuje się O(n)
razy. Sprawdzenie, czy punkty są współliniowe i sprawdzenie, czy
punkt znajduje się wewnątrz danego trójkąta mają koszt stały (jak
wynika z rozważań w drugim punkcie tego wykładu). Zatem koszt algorytmu
trójkątów można pesymistycznie oszacować przez O( n4).
Koszt algorytmu trójkątów nie jest zadowalający. Na szczęście istnieją inne
algorytmy rozwiązywania problemu otoczki, których koszt jest istotnie lepszy.
Pytanie 3: Jeżeli wszystkie punkty zbioru Q, |Q|= n, leżą na obwodzie
pewnego koła, to ile trójkątów trzeba będzie zbadać, aby znaleźć otoczkę wypukłą
tego zbioru punktów?