#algorithm #convex-hull
#алгоритм #выпуклая оболочка
Вопрос:
Онлайн-построение, например, получение входных точек одну за другой и нахождение оболочки для точек, заданных до этого времени.
Я могу сделать это с помощью Graham scan в O(n * nlogn) , или O(n^2 logn) . Но я ищу O(n^2) решение.
Я читал об O(n) алгоритме Мелкмана. Это правильный путь?
Комментарии:
1. правка от 30 апреля 19 неверна; она должна была оставаться «O (n * n log n)», а не «O (n log n)».
Ответ №1:
Это можно сделать, используя небольшую модификацию Graham scan. Напомним, что сканирование Грэхема для статической выпуклой оболочки занимает O (N lg N) только из-за необходимости сортировать точки по углу в начале. Фактические последующие манипуляции со стеком занимают всего O (N).
Следовательно, мы поддерживаем связанный список всех точек, которые мы поддерживаем для сортировки по углу. Каждая дополнительная точка может быть вставлена в правильное положение за O (N) время. После этого часть Graham, посвященная манипулированию стеком, все еще может быть выполнена за O (N) время.
Следовательно, поскольку существует N вставок с O (N) работой на вставку, для печати всех инкрементных выпуклых оболочек требуется O (N ^ 2) времени.
Комментарии:
1. Это был один из моих первых вопросов по S / O, и я так и не вернулся к его решению. Отличный ответ! Я полагаю, что это именно то, что я искал.
Ответ №2:
Первый вопрос, который пришел мне в голову, заключается в том, зачем вам нужно O(n^2) решение, когда вы уже знаете решение, которое вычисляет выпуклую оболочку в O(nlogn) . В любом случае, вы можете тривиально решить проблему с помощью O(n^3) solution, однако я не могу вспомнить ни одного алгоритма, который вычисляет выпуклую оболочку в 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) .
Комментарии:
1. вопрос касался онлайн выпуклой оболочки , поэтому в этом ответе отсутствует суть.