Как реализовать онлайн построение выпуклой оболочки за O (n ^ 2) раз?

Question

Построение в режиме онлайн, получение точек ввода по одной и поиск корпуса для точек, начисленных до этого времени.

Я могу сделать это с помощью сканирования Грэма в O(nlogn) или O(n^2logn).Но я ищу решение O(n^2).

Я читал алгоритм Мелкмана O(n).Это правильный путь?

Answer 1

Первый вопрос, который мне пришёл в голову: зачем вам решение O(n^2), если вы уже знаете решение, которое вычисляет выпуклую оболочку в O(nlogn). В любом случае, вы можете тривиально решить проблему с помощью решения O(n^3), однако я не могу вспомнить ни один алгоритм, который вычисляет выпуклую оболочку в O(n^2).

Если вы используете алгоритм QuickHull для вычисления выпуклой оболочки, то в худшем случае это даст вам следующее повторение.

T(n) = T(n-1) + O(n)

Что разрешает до O(n^2) сложности. Однако в обычном случае вы все равно получите сложность O(nlogn).

Другим алгоритмом является Jarvis March и Gift-Wrapping , который вычисляет выпуклую оболочку в O(nh), где n - входной размер (все точки в выпуклой оболочке) и h это выходной размер (т. е. все ребра, которые ограничивают выпуклую оболочку).

В этом алгоритме Джарвиса-марта сложность в худшем случае может также достигать O(n^2), когда все точки в выпуклой оболочке находятся на границе. Следовательно, в худшем случае вы найдете решение O(n^2). Однако в обычном случае он вычисляет выпуклую оболочку в O(nlogn).