Оглавление
Алгоритм упаковки подарков
-
Алгоритм подарочной упаковки
- Алгоритм Джарвиса Марча вычисляет выпуклую оболочку заданного набора точек.
- Имеет временную сложность O(nh), где n – количество точек, а h – количество точек на оболочке.
- Производительность лучше, когда n мало или h мало по отношению к n.
-
Описание алгоритма
- Работает с точками в общем положении, исключая коллинеарность.
- Модифицируется для работы с коллинеарностью и для обработки вырожденных случаев.
- Алгоритм начинается с точки p0 и выбирает следующую точку pi+1, чтобы все точки были справа от линии pi+1.
-
Сложность и реализация
- Время выполнения зависит от размера выходных данных и линейно зависит от количества вершин оболочки.
- Алгоритм чувствителен к выходным данным, но быстрее, чем алгоритмы с логарифмической зависимостью.
-
Псевдокод и рекомендации
- Представлен псевдокод алгоритма.
- Упоминаются рекомендации по использованию алгоритма и его модификаций.