Университет города Переславля

      "Алгоритмы непрерывной математики"
    осенний семестр 1998-99 учебного года
               С.В.Дужин

                Лекция 6
    Алгоритмы построения выпуклой оболочки на плоскости

На прошлой лекции мы рассмотрели наивный алгоритм построения
выпуклой оболочки на плоскости.
Его сложность O(N^4).

Понятие сложности алгоритма.
Пример: сортировка списка (наивный алгоритм O(N^2), quicksort O(N*log(N))).
Функциональное уравнение T(N) = 2*T(N/2) + O(N).

Более быстрые алгоритмы (сложность O(N*log(N)):

1. алгоритм Грэхема.
2. quickhull ("быстрый алгоритм построения выпуклой оболочки").
3. метод "разделяй и властвуй" (слияние выпуклых многоугольников).

Задачи.
1. Решить функциональное уравнение T(N) = 2*T(N/2) + O(N^k).
2. Определить принадлежность точки данному (в.г. невыпуклому)
многоугольнику.
3. Найти площадь многоугольника, заданного последовательностью вершин.
4. Из данного массива составить замкнутую несамопересекающуюся ломаную.