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).

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

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.

jeżeli nie są one współliniowe, to usuń wszystkie punkt zbioru X leżące wewnątrz trójkąta D(p₁,p₂,p₃),
jeżeli są współliniowe, to usuń ze zbioru X punkt środkowy (z tej trójki).

Poprawność
Po wykonaniu algorytmu, pozostałe w zbiorze X punkty spełniają warunek:
dowolna trójka punktów p₁, p₂, p₃ 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(n³) 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( n⁴).

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?