Опукла оболонка, Детальна інформація

while (p[i] \xF0B9\xF020p[1]) do

begin

p[i + 1] \xF0AC\xF020точка з множини S, для якої кут p[i - 1] p[i] p[i + 1] є найбільшим;

i \xF0AC\xF020i + 1;

print (p[i]);

end.

Теорема. Часова оцінка обходу Джарвіса дорівнює O(N2).

Оскільки всі N точок можуть лежати на опуклій оболонці, а алгоритм Джарвіса вимагає лінійний час для знаходження кожної наступної точки оболонки, то в найгіршому випадку часова оцінка дорівнює O(N2). Обхід Джарвіса є ефективним, якщо кількість вершин опуклої оболонки h є малою у порівнянні зі значенням N – часова оцінка у цьому випадку дорівнюватиме O(N * h).

Алгоритм апроксимації опуклої оболонки

При знаходженні наближеної опуклої оболонки ми розмінюємо точність на простоту та ефективність алгоритму.

Знайдемо мінімальне та максимальне значення х координати точок множини S та розіб’ємо вертикальну полосу між ними на k полос рівної ширини. В кожній із цих k полос шукаються дві точки, які мають мінімальну та максимальну у координату (обирається 2k точок). Обираються також точки з екстремальними значеннями х координати; якщо їх декілька, то обираються дві точки з екстремальними значеннями у координати (максимум обирається 4 точки). Обрана множина містить не більш ніж 2k + 4 точок і позначимо її через S*. Далі можна застосувати алгоритм Грехема побудови опуклої оболонки для множини точок S*.

Приклад. Множину точок S розбито на k = 4 полоси. В кожній полосі обрано дві точки. Для утвореної множини S* побудовано опуклу оболонку.

S, яка не попала всередину наближеної опуклої оболонки, знаходиться на відстані, не більшої за значення (xmax - xmin) / k.

Швидкі методи побудови опуклої оболонки

-



"

$

&

(

*

,

.

V

Z

\

b

d

f

h