Каков наихудший случай для алгоритма раздачи подарков (алгоритм Джарвиса) для вычисления выпуклой оболочки?

Question

Я сделал программу для реализации алгоритма Gift Wrapping для нахождения выпуклой оболочки. Есть ли способ генерировать набор точек, который служит наихудшим случаем для этого алгоритма?

Как я буду генерировать такой случай?

Answer 1

Предположим, у вас есть набор точек - S. Когда на каждой итерации вы вычитаете одну точку из S и добавляете эту точку в выпуклую оболочку, вам нужно проверить каждую точку, что еще осталось в S.

Время выполнения зависит от размера вывода, поэтому марш Джарвиса является алгоритмом, чувствительным к выходу.

Таким образом, больший объем производства - больше времени. И этого можно добиться на съемочной площадке, которая представляет собой выпуклую оболочку.

Вероятно, самый простой способ сформировать такую ​​выпуклую оболочку из n точек - это поставить все точки на окружности.