В чем заключаются ключевые отличия между алгоритмами Грэхема и Джарвиса при построении минимальных выпуклых оболочек?

Ключевые отличия между алгоритмами Грэхема и Джарвиса при построении минимальных выпуклых оболочек заключаются в следующем:

1. Алгоритм Грэхема предполагает сортировку всех точек и последовательное построение выпуклых оболочек для каждого префикса отсортированного массива. 6 Сложность алгоритма — O(N log N). 26
2. Алгоритм Джарвиса концептуально устроен проще и не требует сортировки. 5 Он является двухшаговым и не требует сортировки. 5 В качестве начальной берётся самая левая нижняя точка, которая точно является вершиной выпуклой оболочки. 3 Следующей точкой берётся такая точка, которая имеет наименьший положительный полярный угол относительно начальной точки как начала координат. 3

Таким образом, если точек много и они равномерно заполняют некоторую область, то алгоритм Джарвиса может быть быстрее, если же данные собраны на границе области, то быстрее будет алгоритм Грэхема. 5