4.3. МЕТОД ДЖАРВІСА
Враховуючи той факт, що многокутник можна задати як вершинами, так і його ребрами, цікавим було б визначати ребра ОО замість його вершин.
Теорема 4.6 Відрізок l, який визначається двома точками, є ребром ОО тоді і лише тоді , коли усі інші точки заданої множини лежать на цьому відрізку або по одну сторону від нього.
Теорема 4.7 Якщо знайдений відрізок l = pq, p, q 
S, pq CH(S) 
для будь-якого r S, pq - є ребром опуклої оболонки, Sp,r,q 
0, Sp,r,q - орієнтована площа трикутника.
Припустимо, що знайдено найменшу в лексографічному порядку точку р1 заданої множини точок.
Ця точка явно є вершиною оболонки. Далі необхідно знайти наступну за нею вершину р2 опуклої оболонки. Точка р2 - це точка, яка має найменший додатній полярний кут відносно точки р1 як початку координат. Аналогічно наступна точка р3 має найменший полярний кут відносно точки р2 як початку координат, і кожна наступна точка опуклої оболонки може бути знайдена за лінійний час. Алгоритм Джарвіса обходить кругом опуклу оболонку, породжуючи в необхідному порядку послідовність крайніх точок, по одній точці на кожному кроці (мал. 4.7). Таким чином будується частина ОО (ламана лінія) від найменшої в лексографічному порядку точки (р1 на мал. 4.7) до найбільшої в лексографічному порядку точки (р4 на тому ж малюнку 4.7). Побудова ОО завершується знаходженням іншої ламаної, яка виходить із найбільшої в лексографічному порядку точки до найменшої. Виходячи із симетричності цих двох етапів, необхідно змінити на протилежні напрямки осей координат і мати справу з полярними кутами, найменшими відносно від'ємного напрямку осі х.
Мал. 4.7. Побудова опуклої оболонки Методом Джарвіса.
Так як усі N точок множини можуть лежати на її ОО (бути її вершинами), а АД витрачає на знаходження кожної точки оболонки лінійний час, то час виконання алгоритму в гіршому випадку рівний О(N2), що гірше, ніж у АГ. Якщо в дійсності число вершин ОО дорівнює h, то час виконання алгоритму Джарвіса буде О(hN), і він дуже ефективний, коли апріорі відомо, що значення h мале. Наприклад, якщо оболонка є многокутником з довільним постійним числом сторін, то її можна знайти за лінійний відносно числа точок час.
